Go to bestbuy and play with some stereos if you want but do not buy there. Buy from amazon or somewhere on the internet. I'd stick with pioneer or alpine as some previous people stated. I'd personally go with pioneer for about $200 online you can pick one up with built in bluetooth, usb port, and aux in (the same one at best buy was $450). This way you can plug in the phone with the dock connector and it will charge and you can control the ipod through the ipod or stereo. You can change this preference through the press of one button. If you want to use pandora, lastfm, iheartradio, then select control via ipod/iphone and they will play through the dock connector with out messing with anything controlling it through the iphone.
I said go with a stereo with built in bluetooth because no car stereo can play phone calls through the dock connector because of apples api's. I know this as I searched for a month before I hooked up my stereo and my buddy's last week. The ringtone will play through the dock but once you answer voice won't. Then all you have to do is turn your bluetooth on (easy if you have sbsettings) and phone calls will automatically route through bluetooth and the music will pause automatically when you have a call incoming, outgoing, and even go quiet for a second to hear your sms tone. Pioneer units that have bluetooth built in, will have a mic built in too so you can position that anywhere and you could leave phone in your cupholder.
Once you sync you phone through bluetooth the first time, the phone and stereo will remember each other, so all you have to do is turn on bluetooth and not worry about selecting a device each time. When you have an incoming call you can use the stereo to answer or pick up the phone and one screen theres a button that says phone, click on it if you don't want everyone in the car to hear your conversation and you can just use the phone.
As for the stereo hookup its the same as any other stereo if you have hooked one up before. If you haven't its not hard. Set aside a few hours on a nice day and save yourself the $100+ install fee everywhere else will charge you and just search the internet for the an install guide.
**Anywhere I stated ipod I also meant iphone. Hope this helps.