First stuff that helps stability then hopefully performance and then high-res resolution if the game is older. Content restoration if if it's available too. Otherwise a texture pack or something that tweaks or otherwise adds a neat mechanic is welcome too.

Depends on how many times I've played the game. First playthroughs I usually just go with bugfixes and content restoration mods. Skyrim was an exception, since I knew from experience the kind of immersion mods I'd want on a TES game, so I added them straight away. For games like Baldur's Gate that I've played a lot I'll mod much more heavily, with new quests, companions, AI changes, ease of use mods etc.

Graphics mods, and anything that makes the game more *playable*. See older FPS's where you couldn't rebind the keys, or System Shock which was unplayable for me in the 90's, but now works okay with the mouselook mod. I usually don't bother with "re-balancing" mods, or "bug-fixes" mods, as I've almost never had any problems even with games reported to be bug-ridden, like Vampire the Masquerade: Bloodlines.

In this order:
- Fixes,
- Restorations (KotOR 2 and Fallout 2 restoration projects are prime examples),
- Storyline additions.
Mechanics, as long as it's not broken beyont being unplayable, rarely bothers me.

In rough order:
hi-res and/or wide screen
unofficial patches (non-game changing)
gui/hud improvements
texture/graphics improvements

I used to try out exta story mods and conversions but I have too many games in my backlog now, so making the ones I've got any longer isn't a grat idea ;)

I might throw in an "unfinished bussiness" style mod.