Depending on your budget, look for something in the Pioneer, Clarion, Kenwood, Sony lineup that fits your needs for the cost. As for a "premium" sound without amplification, I don't think that is achievable. Then again, my old hobby was Pro Sound as a mobile DJ and sound technician for a country music band, so I need a lot of power to get loud (dang near deaf FTL

)!
As for speakers, you will get a million different answers. Infinity Kappas are too dang harsh on the highs to suit me so I won't recommend them. Polk, Boston Acoustics, Alpine, Pioneer are a much better "off the shelf" buy. Regardless, a head unit (deck, cd player, etc.) with a decent 4 channel amplifier should and aftermarket speakers be your starting point. If anything, I would recommend getting better speakers for your front doors than in the back because that is where your main stereo image will come from. If I had to split the distribution on speakers, I would budget 90% of my money for the front speakers and 10% for the rears. I rarely run rear speakers anyhow, but that is besides the point.
For your sound to be really complete, I recommend a subwoofer, but many of my muscle car buddies do not want to add a subwoofer. A single 10 on modest power will help blend things together. Something like a Resonant Engineering RE RE 10" sub with about 300 watts going to it will do wonders for your upgraded sound. There is a large choice of 10" subwoofers to choose from and there are many decent alternatives to the traditional car audio subwoofers. A Dayton HO sub from parts express comes to mind here.