We have a table of about 48" by 72" and it works pretty well for armies around the size you propose.
Have alook at:
http://forum54.oli.us/index.php?topic=4554.msg30566#msg30566To get a feeling of the tabel, just look at some of the battle reports and the outcome to see what´s possible and what´s not.

Depends extremely on what you want to play!
If you like long dinstances many para-deployments, you can try for a field a bit broader to lenghten the distances.
If you only play three-player games you may want to us a board of approx. 60" by 60" I think.
On an square you will have it easier to managa to get the distances even for everyone than on a rectangle