After trying 4x5" and 8x10", I felt that 8x10" was more intuitive to me, and I love the contact prints, but I've also come around and found a place for 4x5". A great thing about large format is that lenses can often be used on different formats, so it's not too hard to expand.
You can get a 4x5" reducing back on many cameras, and Toho Shimo even makes a reducing filmholder that will hold a 4x5" filmholder inside the reducing holder, for cameras that do not have reducing backs.
What camera--depends on your priorities (cost, weight, precision movements, portability, system accessories, expandability, rental options, etc.). Again, check out the reviews at largeformatphotography.info.