I think one of the biggest questions is what all you want to keep. If you want to keep the factory amp and speakers, I think you might be more limited in what you can use for a head unit that will interface well. On the other hand, if you are okay with replacing the other components you have some more options and can tailor the system better.
All that said, I don't think the factory stereo is nearly as bad as people make it out to be. Any aftermarket exhaust drowns out a fair portion of the lower frequencies. I've replaced pretty much everything in my car at this point (it had a full aftermarket system when I bought it, but it was sloppily put together). The speakers are pretty much all Kicker brand at this point (tweeters in the dash, door speakers, and the sub between the seats). I don't have the little speakers behind the seats anymore. I have an Alpine head unit and amp that mounts under the passenger seat. I like the setup because I could tweak and tune it. I got it sounding good sitting in the garage and was fairly happy with it, but as soon as I start my car all the bass just falls out. My dad had a totally stock 03 for a while and the I thought the stereo in it sounded just as good and even had more low end punch to it than my setup.