I need some advice on what to buy first in this game if I want to play respectably but cheaply. Which starter deck is the best and ultimately the cheapest to build on?

You're probably better off playing a bit with the default decks and getting a feel for the game. Make decks using those phantom cards. Play against "anyone" and see what sort of cards people use against you. Then take another look at the starters. Most would say they're not so great to build upon. You're probably better off buying individual packs and selling cards. Or if you don't like that randomness, try one of the "cheap deck" builds in the forums, buy gold, and try to put it together in the marketplace.

I base my comments on info from TFWinfo.com I haven't actually purchased a starter pack, so I don't know from personal experience what is in them. In the end everything depends on personal preference.

According to TFWinfo.com each starter contains 3 rares and 9 uncommons, the rest is commons.

MF seems to be the "worst" starter. Compared to the other starters the mf starter contains one more 7 cost domain base. As we all have 5 of each 7 cost domain base (which is the max) it would seem that you would get 1 card less if you buy the MF starter than if you buy a starter of another domain. Also the MF starter contains some cards I find rather useless, for example 3!!!x Homeguard.
When looking at army themes I believe MF actually lacks a decent theme compared to the others. E: Ocean/desert, S: Treants, D: Death/sacrifice, M:?Dwarves?

So if you have decided to buy a starter my advice would be to avoid the MF starter.
But as I mentioned earlier it all depends on personal preference.

~Wombat in combat killing evil dwarves (Wicked)~

I can tell you what I did and worked really well for me.

I bought 1500 gl and spend it in 1 keep cards, 1 Domain League and used the other 500 to buy some commons and buying more packs in the Domain league. As you should know Domain is 500gl and you get to buy 1 more pack every week so there are 3 extra packs for 450 gl total. I lsot in keep cards and did very bad in domain league but that’s not the point because I get some good cards.

Between Domain and Keep cards, for me been a newbe, the one that really helped me was Domain league. Having a lot of cards of the same domain helped me a lot to build my first competitive deck. It was a MF deck based on Bard’s inspiration and Tales of (I don’t remember, tales of “something”). In a time where every body was playing sylvan or dark legion decks. And sylvan players were not using their global disenchant me deck end up been pretty good.

So I think Domain league is the best option. But don’t choose elemental, in my personal opinion I think that elementals need 3 dew mogi to be effective in early game and to get 3 of those would be just too much luck.