So I was looking for something today and ran across my old CD for Morrowind. I decided to install it just for fun. I've already installed a couple mods, Better Bodies and Better Clothes, and that really does improve the look of the characters. Is there one for the heads too?

The problem I've run into is that I'd also like to run Morrowind Graphics Extender, but after downloading and installing the latest plain-Morrowind patch from the Elder Scrolls website, I find I'm still not at a high enough patch level to run the MGE. I believe it requires 1.6, I'm at 1.2. Something like that. Looking at the download page, the only 1.6 patch is for Bloodmoon (and the error message I get refers to Bloodmoon as well) but I never got Bloodmoon. Can I install that patch anyway, or is there a 1.6 for the unexpanded game, or do I need to get Bloodmoon first?

Also, do you have any other suggested mods to improve the appearance of the game? Particularly the walking and running animations get to me.

I'm experiencing a slightly similar problem with MGE and patching. I have Morrowind + Bloodmoon with no tribunal and the patch updater won't recognize "Old files," to install the patch. As far as MGE goes anyways.

And yes, I'd also like new faces and running/walking animations too.

Well, if your version is 1.2.something you are out of luck. Sort of. Version 1.6 is basically a different game! What I mean is that the "add-ons" Tribunal and Bloodmoon also actually change some aspects of the game engine. So what it boils down to is: no there's no patch that turns a 1.2 into a 1.6 - except "Bloodmoon". Same goes for Morrowind + Tribunal (you'll end up with v.1.3.something if I remember right). I would just get myself the goty if I was you. In germany, that'll cost you 3,99 € (for instance at Amazon)
The expansions alone would be worth it (and - ooops - a used copy costs 0,99 € at trade-a-game). If you look around, and your english is good, you may also get the english goty while you're at it: a lot of plugins only work with the english version.

Thought I'd bump with with an answer to your question about heads and animations:

First off, I would personally Recommend http://www.gamesas.com/index.php?/topic/1057651-wipz-westlys-head-replacers-still-working-on-a-better-title/, which is pluginless and replaces all of the Orc, Breton, Altmer and Nord heads and hairs. It looks much better then Better Heads, and stays truer to the vanilla designs, but not all of the races have been done yet, so I would recommend using http://planetelderscrolls.gamespy.com/View.php?view=mods.detail&id=5883 along with it.

If you want heads for the PC, look no further then http://planetelderscrolls.gamespy.com/View.php?view=Mods.Detail&id=6173, and lastly, Dirnae has replaced some of the vanilla animations http://www.gamesas.com/index.php?/topic/1066248-some-more-stuff/.

Best thing is that none of these mods require Bloodmoon to work, so if you haven't gotten GOTY yet you can atleast use these.

Hope this helped