Yeah, a stock deck will not do any improvement in sound so that will definately need to be changed. If you want the best sound, get a 4-Channel amp and hook up a set of components and 2 ways for your highs/mids and you'll be set.
Then you can get a sub/amp setup for your lows.
Prices:
headunit/deck : depends what you want... something basic can range from 50-100 but something higher end like a double DIN can range from 200-500 or even more if you want NAV and stuff.
4 Channel amp : 200-500 again depends on where you buy it and what brand.
components and 2 ways : 200-300
sub/amp: depends on how much power you're looking for.. 100-800 for the setup
all those prices don't include labor so expect to pay labor charges as well. If you want the best of sound, go with JL Audio subs and amps and a good brand head-unit such as Alpine, Pioneer, etc.