One important piece of data that I didn't see (or missed) is the fact that most 3.0's are running a 2:1 gear ratio, not the higher ratio's everyone else is used to. So a 20-something prop isn't necessarily too much. FWIW, my little 17' Bayliner with 7 adults, a 21" prop, and 4400' altitude would plane out in less than 5 seconds and hit about 43mph. (with just me planing was almost instant and would hit 48mph on a good day)
That 21'er will be heavier, but with some extra air to breathe in (lower altitude) to compensate, 35mph in a 21'er doesn't seem all that "not right" to me. Those little 4 bangers have more grunt than most people give them credit for. They're biggest power problem is lack of high rpm power.
As for gas mileage, I routinely got better than 6 mpg out of ours when cruising at around 23 mph...