If you're playing in the UK, EpicUK appears to be a vibrant community, but they use their own lists for tournaments.  I'd recommend working with those lists if you're in the UK. ÂÂ
Ordering from many online retailers can snag you a discount.  I don't know if Neal at the WarStore does a discount for Specialist Games, though. ÂÂ
If you're in Canada, or don't think international shipping would be too bad, you can order from
www.gc-minis.com.  They do a 20-25% discount on Specialist Games stuff.  Of course, that still ends up with it being ludicrously expensive, but it's
less ludicrously expensive.  I recommend them - a 25% discount is nothing to sneer at. ÂÂ
Ebay and Bartertown both see a decent amount of Epic stuff for sale (especially if you're in the UK for ebay).  You also might be able to buy some stuff from people on here - many have waaaaaaaaaaaaaaaay too many spare plastic Rhinos and Land Raiders. ÂÂ
In regards to unit selection - a Battle Company box, some Thunderhawks, some tanks and some Land Speeders will send you toward an effective path.  Terminators are nice (and nice models, IMO).  Titans are fun (but are now ludicrously expensive).  Some Predators wouldn't hurt.  People swear by Razorbacks.
They're are also a few variant Space Marine lists kicking around the forum (including my own), but I wouldn't recommend them as a basis - you're better off sticking with the most official lists you can get at first.  That way you can play with almost anyone.
EDIT:
The square base thing is not a problem - look inside the Epic rulebook, and you'll see it's one of the mentioned basing options.  It IS a pain in the ass to paint, though.
EDIT 2:
Oh, in regard to painting - I find there are two basic ways to do it - prime the color the marines are going to mostly be (usually with a wash to get in the cracks), or prime black and drybrush over the top.
I'm not sure which works better myself, but it's likely best to decide before painting your entire army.