I'm pretty sure you're right, the stock door speakers are 5-1/4", but you can put 6-1/2"s in there without much work. I've got 6-1/2s in mine and I don't recall doing anything other than maybe drilling new holes for the mounting screws. As I recall, you have to be a bit careful with how deep the speakers are, as the doors don't have a ton of room for speakers with big magnets. In the past I've used Crutchfield's database for figuring out what will fit.
As for the rears, there are plenty of speakers that are marketed as both 5x7" and 6x8", with two sets of mounting tabs. I don't see any reason why those wouldn't drop right in. Big magnets may again be an issue - I've seen posts here on Corral that said a seatbelt bracket might interfere.
For budget, I don't think you'll have any issue finding good speakers (new) for $75/pair. Doesn't sound to me like you're looking to create an audiophile type setup, you just want to replace your 30-year-old speakers with something new. When I put new speakers in my little beater Subaru about 18 months ago, I picked up two sets of 6-1/2s at Best Buy - Pioneers and Kickers, both on big time mark-down. As I recall they were like 50% off and 70% off. I don't think either pair cost me $75.