Check out the Pioneer DEH-P800PRS or DEH-P880PRS. Neither are made anymore but can be found used on Ebay. You'll be amazed at what the 16 band auto-eq will do for your sound, and the output is crystal clear. It's the best option short of the $1000 units like Alpine F1 and Pioneer Stage 4. DO NOT HOT SWAP THE RCA CABLES or you will blow a pico fuse on the main board that requires soldering to replace. That's the only issue with these decks. You will need a $10 cable to hook up an aux input. There is no built in amp. I recommend an Eclipse class A/B (NOT the new class D - they have 1% distortion at rated power).
I am running an Eclipse PA5422 for my highs. I think I paid about $70 for it. (It was around $400 new.) You could carefully run the factory speakers off of something like this until you upgrade them.
Then check out Polk's MM coaxials. They are outstanding for the price.
For a sub, I recommend Dayton Audio's Reference High Output line, the bigger the better, in a sealed, 50% fill box.
The sub amp can be anything decent, but the old Rockford amps like the 125.2 or 225.2 can be had for very cheap on eBay. Lots of power for the price.
My setup:
Deck -Pioneer DEH-P880PRS
Front - Polk MM651
Rear - Polk MM691
High amp - Eclipse PA5422
Sub - Dayton Audio Reference HO 15" in 1.7 cu ft sealed with 50% polyfil stuffing
Sub amp - Rockford Fosgate 225.2 (from 1998!)
Car audio was one of my hobbies from 1996 up to last year. This setup killed that hobby, because I want for nothing now. It's perfect.
The deck and amps came from eBay used. The speakers I bought new.
My 3 cents.
EDIT - The DEH-80PRS is the current model and has the same guts, but I read a few reviews that complained that the face felt cheaply made. It DOES have a built in amp. It's about $250. This is what I recommend if you don't want to buy the previous model used, or don't want to have to buy an amp right away.