I have a few thoughts, some of which are along the same line of what you all have said:
-Shake up the Wheel values considerably. I'd be fine with sub-$500 values and I'd be fine with >$1000 values. Do this for every round. Mix it up. Make it interesting.
-Replace the Prize Puzzle with a "$5000 bonus" opportunity. One of the first three rounds has a bonus attached - either one of the standard bonus categories (Clue, Fill in the Blank, etc.), the Puzzler (I know that wasn't hugely popular, but it isn't the worst idea and adds variety), or a bonus question appended to a regular puzzle. This is substantially less of a hit to the budget than the Prize Puzzle, both because of the maximum value ($35,000 minimum now for a five-day week vs. $25,000 maximum with this) and the fact that it won't be won every day. Plus, it breaks the game a bit less, it's not in the same round every day, and probably encourages more variety and creativity with the puzzles. It would also potentially be a surprise in the first two rounds if it was the Puzzler (I would go back to not having it announced until after the puzzle is solved) or the bonus question, which means that you won't have contestants solving a puzzle for $500 over and over again.
-Drop the first two Toss-Ups. Either keep the Triple Toss-Up (and make it $1000 apiece with a $2000 bonus for the sweep) or go back to one TU for $1000 (both options before R4).
-Figure out some way to offer better category options for the Bonus Round. After Season 35 (the first season where this was a feature), the options quickly went downhill and have stayed there since. Sure, contestants often make terrible choices, but that is no reason to have Thing(s)/Phrase/(Third option) 90% of the time.
-Add some more variety to the Bonus Envelope options. We've gotten confirmation that the car returned from this past week's tapings, so that's a start, but even then, there are only five given options at any one time (40K/50/75/Car/Top Dollar). That's pretty slim pickings. I don't think we need to go back to Shipboard Parties and Rolexes again, but there is definitely room to expand. I like others' suggestions of a smaller prize or two ($20-30K) paired with some cash.