I won't reply on your first statement, as I have no experience with Paladins myself. But bards, well, in the hands of a skilled player they can annihilate every threat in a matter of seconds. Many people think the bard is a weak fighter/mage, but in fact he's an extremely strong. First, the bard has a rogue's experience table and gets level-ups extremely fast, giving him access to level-6 spells in the early state of the game. A bard's thac0 and spell selection will always be weaker than that of the F/M, but you have to learn to use them in the right combination. The quick level-ups also allow you to get your first HLA very quickly, and UAI overwrites all item restrictions, so your bard can actually wield Carsomyr or the Staff o/t Magi. A dualwielding bard can get up to 8 attacks per round with Improved Haste, can lay Time Traps giving him a 10-second personal Timestop spell, can protect himself from all possible threats with Stoneskin, Spell Immunity, Mirror Image, ... The weak thac0 can be a problem, but there's nothing Tensers Transformation can't do. If you have a bard in your party, he can also use the bard song to give you additional bonuses (the Skald song gives all your party members +4 to Hit and +4 damage!). I strongly advise you to solo a blade or skald through the game. You'll have to learn to use every resource available, but the satisfaction you get from it is heavenly.
"We are at a very serious moment dealing with very serious issues and we are not focusing on the name you give to potatoes" - Nathalie Loisau