Should I consider rewiring the truck when I get the new deck?
If you're talking about the speaker wire, the factory speaker wires are plenty. I would only run new wire if your going to power the speakers with an external amp.
16awg wire is plenty, even for very high powered speakers.
If you don't have to have the high dollar head-unit, you can build a much better sounding system on the same budget. just a thought, depends on what interests you more.