I play a Thief and have decided to throw some Destruction in, so my Destruction is low, so I'm struggling. What enemies have what magic resistances? For example, what's resistant/vulnerable to Frost magic and so on?

For Frost? Ouch, almost everything in Skyrim is resistant to it. Regardless, its very useful for slowing things down.

Nords
Giants and Mammoths
All Draugr
Frost Trolls, Ice Wolves, Snow Bear, any creature/animal with frost/snow/ice in its name
Vampires and pretty much all undead

Well Trolls and vamps have low fire resistance.

I hope someone has some good tips on this because I'm finding leveling destruction fairly slow. My research so far indicates that this is just how it is and there is no really fast way - you just have to use it a lot. So I'm targeting big creatures using my highest level favourite destruction spell - currently fireball.
To try to level destruction, the best I've come up with is targeting the giants and mammoths - and dual casting fireball at them standing on a rock outcrop or using Become Etherial to run away. Fire works well on giants and mammoths - but taking out 4 giants and 4 mammoths only took my character up 1 level in destruction (to 65). Now the Whiterun area is giant and mammoth free until they respawn. I'm also using fireball on any goats etc that cross my path and saving the goat horns for the HF building.
Frost trolls might be better to level destruction if you can find something to stand on to attack because they regenerate. You could blast them until near death, then wait for regeneration and repeat. I haven't tried this myself - I kept going until they were dead. There are lots of frost trolls at Labyrinthia.

When you use a Destruction spell on a valid target, you get XP equal to the base mana cost of the spell used. The more mana the spell costs, the faster the skill levels. For general use, you'll want to use Shock element spells, as they tend to have higher Mana cost than the other element. This actually works out, because there's only one creature in the game that has an innate resistance to Shock Damage (the Shock Atronach), and you hardly ever see it. Be warned, though, that I have had enemies resist shock randomly; I'm assuming that they had a Potion of Resist Shock in their inventory that they used when they saw me using Shock spells.

Anyway, since you're a thief, Runes are going to be a good way to level, at least in the early Destruction levels. Just sneak in and throw it in an enemy's path. Just be warned that I've heard that Runes are a bit bugged when it comes to stealth: apparently, once they go off, the enemy knows exactly where you are when it goes off, even if you're hidden. Cloak spells are also nice, but while you could sneak up to an enemy and electrocute something to death, I have no idea how they will react to the damage if you're hidden. They may turn right to you, or they may go wandering off out of range of your cloak.

EDIT: Also, keep in mind that the game doesn't care how much damage you inflict; all that matters is that you use the spell and it hits a valid target. Wandering through the wilds zapping every bunny, fox, elk, moose, etc. will earn you plenty of XP. Even more so if you're using the Mage stone. Bandit camps and ruins are also nice; most enemies will be pretty weak, so you can take them out easily. Just don't kill the boss, and they'll respawn pretty quickly, allowing you to come back in 10 days and do it again.