I agree with Ralph, though most of my printing is done via contact prints and I am primarily shooting 8x10 these days. I order my film and supplies online as opposed to having the local camera store order it for me (they don't have anything larger than 4x5 (filmwise) in the store anymore).
I can understand why you feel that way about 4x5. I shot my first 4x5 slides recently and looked at the result and thought, "Cute, but small." Seems that I never think that way when doing B&W, even when contact printing. Part of it could depend on what you're going to do with it.
I used to shoot 5x7 and love the size. Had a monorail B&J and a car, so it travelled a bit. If you're going to carry the thing outside at all away from your vehicle, size issues will play a HUGE role.
If you haven't played with 4x5 much yet, then enjoy it first! It changed everything about the way I shoot. I worked on 4x5 for about 5-6 months before I dusted off the 5x7 and put it to use. Making FNG mistakes is a lot cheaper - like the time I went to a Shuttle launch with the film loaded in backwards. Remember, I said cheaper, not less of a heartbreak.
Remember that you'll be using smaller f-stops with the 8x10 than the 4x5. As such, you'll need to use longer exposures and subject movement can become a real problem. Plus rigidity becomes a much bigger issue. You'll need a *very* sturdy camera head and tripod, and if you use longer lenses you might need a monopod for under the front standard.
I vote for 12X20....
Seriously, I have used 4X5, 8X10 and 12X20. I find that 4X5 enlargements are virtually indistinguishable from 8X10 contacts. 5X7 enlargements can look very good at 16X20 print size.