Paladin's play exactly as they are intended. They're extremely straightforward. You use the halone combo for threat and damage reduction, shield lob to get initial threat from a distance, and flash for AoE threat (or to blind a single target). They don't have a secondary resource to worry about (wrath stacks), their abilities are on demand (no build up, no using abilities in combination with others to maximize effectiveness), and their cooldown abilities have a decent duration so you can be a little sloppy when timing their use.
Your biggest problem is that your gear is very weak compared to those who are pulling threat off you. Get a better weapon and you should be ok. If you're having trouble with ifrit, garuda or king mog for some reason, you can always get the crafted HQ lvl 70 sword. It's pretty cheap on the market board (at least on my server). And if you want to save more money, farm up enough philo tomes to purchase the 9 coke required and see if you can find a crafter to make it for you. Just make sure you're getting an HQ version, the normal version is junk (just like normal crafted anything...) With the changes to threat in 2.1, this should be all you need as long as your rotation is good. If you're still having trouble after this, make a post on the tank forum asking for advice, you're likely doing something wrong.
The intended design of paladin is pretty sound. Their base mechanics are very simple compared to any other class. But this is so you can focus on other aspects of tanking, IE: positioning enemies, picking up adds, dodging attacks, etc.
War is a (little) more involved tank for those that prefer this style. It's still not as complicated as a melee DPS, but they've got 3 combos to work with, need to manage their wrath stacks to use some abilities, and inner beast's duration is pretty short so you need to be more precise when using it to reduce heavy incoming attacks. I would say if paladin is boring you then you may find warrior more interesting.