Go as big as you can, you'll always want to upgrade. Ive got a 130g, a 55g and a 48g which just about copes with all the cichlids i desire!
Good starter cichlids are Keyholes and Bolivian Rams. Very hardy and peaceful. They do lack colour and the personality of some of the bigger and more difficult guys though.
A good thing to do is to get one of each sort as it generally avoids breeding unless you have two very similar species (ie convicts and sajica).
Suitable for a 55 would be convicts, sajica, blue acara, ebjd, keyholes, rainbow, bolivian rams, firemouth, angelfish, the list goes on. You couldn't put all those types together though of course. I would stick to things that are not likely to get above 6"
You could probably go with a couple of 6" with a trio around 4" with no probs.
A peaceful set up would be an angel, keyhole, bolivian ram, and maybe a cockatoo cichlid and similar (5-6 individuals).
A more aggressive would be an ebjd or blue acara, female con or sajica, rainbow and firemouth. (4-5 individuals).
A 75 would give you more options of course.