I'm stuck between making a Mage or a warrior

Which one appeals to you more?

Well, you could try to wield a sword and a shield, dress in heavy armor and join the companions for starters. Melee is good for beginners. Up to you though.

Well i suggest a warrior because wizards are cheap ( no offence to all wizards)

You don't have to play only one character like i do, you can have multiples characters going on at the same time. It's the best way to see what playstyle you like.

Or play a hybrid like a Spellsword.

Was about to comment this.

Do both. Why settle for one? A Battlemage? Paladin? Nightblade for a more sneaky variant?

Between Warrior and Mage I would say Warrior but like some other already said, you can go with Spellsword.

Can there be any more terrible master of the science of war than a battlemage? I think not.

If its your first character then I would definately go with a warrior. They're pretty cut and dry. Mages are more tactical.

mentat...

Thats pretty much true. The only good effective magic is Enchanting because you can use it on swords and armor. Not just that but you can use Enchanting to fortify the Archery and One Handed, or Two Handed skills to do more damage. Also you can use Enchanting to fortify smithing to raise your heavy or light armor rating higher. I think magic can go well with melee, so long its balanced. But I don't stick with one. I mainly use melee though because spells don't do as much damage. But Restoration and Enchanting are the most useful to go with melee.

Nightblade that also occasionally goes Spellblade.

One of the most ridiculously overpowered characters I have created was a Nightblade: Light armor, One-handed weapons, Archery, Illusion and Alchemy were the main skills. And sneak of course. Only Dragons were a slight problem since my aim with mouse is not very good. For other enemies this rarely was an issue since once I mastered Illusion they never really knew where my character was.

However, I'm finding it hard to really mix melee fighting and spells. Eventually I just drop the spells since sword gets the job done much easier. Perhaps it would be different if I could block and still have a readied destruction spell in the other hand. Does anyone have any good tips on how to properly play a warrior-mage?

Well, there's a certain http://www.nexusmods.com/skyrim/mods/9247/? that can help with blocking. I also suggest investing in restoration magic, mainly wards and projectile based destruction magic, rather than stream based. Aka. Use fireballs instead of flames.