I usually go for 192k- which will be about 5MB for a 3 minute song.. Generally no one will complain about that. I personally feel you begin to lose too much detail below that.
You have bear in mind that with a lot of peoples' dialup connections, more than 5 or 6 MB's and they'll likely go look for another song to download, or they'll just be very selective about who they'll generally listen to. It's a shame, but it's also a reality.