This deserves a point-and-click adventure game.

I presume you know of OpenTTD, though it's not really an "other game".
Another open source one is Simutrans.

Yus.

Head: 40 tris, 32x32 pixels
Body: 200 tris, 64x64 pixels
Pistol: 52 tris, 32x32 pixels
Rifle:  46 tris, 64x64 pixels
Blend here.

...full games that retail for $35 might represent months or years of work from a lot of people.

$35 of game serves a few hours of play time.
$35 of graphical assets serves a few months or years of game development time.

Looks really smooth. Can't tell from the gif that it's tiles-based movement.
Any demo soon?

Right, we'll add a food meter that slowly goes down no matter what you do.

Blue game-developer needs food badly.

[Slow:]

Slow: Finger-lickin'.

[siskavard:]

siskavard: I hope he has a special ability where he can "rain" on people below him as he hovers.

You are arousing my roguelike lust right now.  I want you to know that.

One where you have to escape a slowly flooding dungeon and you can open locks or dig holes through to the next level down to buy yourself some time but in doing so risk cutting off an escape path as you can only spend a limited number of turns in flooded tiles before drowning and risk getting carried further down into the dungeon by the current.

Very clever, albeit disturbing.. 

Surf life savers do have a life outside of work you know.

If anyone got more links for prices on companies that does graphics please share

If you want good, consistent art I would probably recommend looking for an artist or two, rather than an "art" factory like that Heavy Cat appears to be (And seriously, a graphics company with a website that looks like that?).

If it'll be usable for sprites bigger than 6x5 pixels then I'll be interested.

Modular ships.

Parts.

That really makes a massive difference. 10x times more realistic/delicious. 

This entry is so pathetic..

So pathEPIC.

You Star Aryans sure are plentiful. Are all the star systems of the great void overrun with your ilk?

I quite like the look of the environs. They are simple and rather crude, but charming.
The characters could be likewise if their proportions and poses were tweaked to be more natural.
Looks like an early nineties shareware game, which is a positive as far as I'm concerned.

Ore Chasm. 

I'm looking for a good MS-paint like pixel art program

But if you insist on an mspaint-like program there are the major desktop environment clones gnome-paint (Gnome, obviously and pretty much a direct clone of mspaint) and KolourPaint (KDE, not quite so cloney). There's also Pinta which is styled after and somewhat-based-on Paint.NET.

If you want an actual pixel editor (ie. indexed) there's grafx2 as Hoope suggested and mtPaint.

If you are running on x86 you can also use Wine to run windows programs. I use GraphicsGale through Wine myself. Apparently mspaint works under Wine too if you happen to be that obsessed.