5 gallons are the most common and the most available. Be aware there is only a very small group of mini-fridges that are tall enough to put a 5 gal corny in without having to modify the freezer compartment, and that can be tricky. Pretty much if it has a freezer in it, they are not likely to fit. I don't remember the models that do fit cornys, but you can google it. They are hard to find though as people who keg snatch them up off the used market pretty quick.
Going with a kegerator, or modifying a chest freezer is the options most brewers end up going with. If space is a concern the kegerator is better suited. I ended up with a scratch and dent (minor) kegerator after spending about a week trying to find a fridge.
The overall cost can get up there pretty quick with kegs, refrigeration, co2, regulators, taps. Most of that can not be avoided with the exception of starting of with picnic taps till you can afford some decent faucets. Don't skimp on faucets, wait till you have the cash and get the Perlicks. Kegconnection is a good source for the kegs, co2, regulator set-up, etc and they are a vendor here, on ebay, and through Amazon.
Read up on it and take your time. There is some good info out there, and plenty of people to ask questions when they arise.
Cheers