In answer to you question:
-You should stick with Gondor. Gondor has solid warriors,(relatively) tough cavalry, access to warmachines and plenty of Heroes to choose from (ranging from cheap, effective leaders to high end Über's like Aragorn and Boromir). Rohan is a difficult army to use but is cavalry centric. However many of the models from both armies are fun to paint.
-If you take my advice on sticking with Gondor then I advise you to obtain the following- Faramir (on foot and on horse), a box of Rangers of Middle Earth, a box of Gondorian Knights (and (optional) the 'Gondor in Flames' sourcebook).
Buy the Rangers and Faramir first (so that you get a good mid-level hero and more importantly, have 49 men (1 under the limit of troops in a 500< point game) since numbers are important in SBG. This will provide you with a good starting point with the cavalry being your next purchase.
-Once you have a 500 point force you could consider buying any of the following: Another box of WoMT, Osgilath Veterans (they are a perfect compliment to Faramir), Citadel Guard, Fountain Guards, fiefdoms troops (Knights of Dol Armoth etc.) or another box of Knights.
After 750+ points though, the rest is up to you and how you want to build your army.
Good Luck.
Yours
TDoM
EDIT: This is the advice I gave to my friend who started Gondor and his army wiped the floor at the SBG beginner games and still continues to provide a challenge for my goblin tactics.
