the first thing you need to do is figure out which wireless provider you want to go with. personally i've always liked verizon as i get signal just about anywhere but the only provider left which currently offers unlimited plans is sprint. their network coverage is limited and their speeds are slow though. i was lucky enough to be grandfathered into verizon unlimited before the tiered data changes hit.
as for tethering a phone to a laptop: i think any of the smartphones can do it. most wireless companies will want to charge you like $20 for this service though which is an add on to your existing data plan. with android phones there are ways to get free tethering without having to resort to paying a provider for the option.
any phone which accepts microsd cards can take your music collection with you. i believe i have a 16gb card in mine right now (and like 4gb internal).
battery life is where you might not be as impressed. think of current generation smartphones as small computers, they are not going to go days between charges like any older phones you may have had. using 3g, bluetooth, wifi, or having the screen on constantly will drain your battery in about 6-8 hours easy, or faster depending on what you are doing on your phone. you can counter this by buying a bigger battery (such as the 2150mah ones). i've heard that some of the newer gen dual core processors are a bit more energy efficient than the older versions so you may want to look into these.
i've heard of people getting several days between charges with very minimal use. everything depends on how you use your phone.