Karate vs. Aikido? I say --> Kung-Fu :=)
ZenLateralus: absolutely right about 'American-karate' - it's mostly power, nothing but different katas, and it doesn't by itself improve your strength - only shows what you can do with it basically.
Karate is not too, for a lack of a better word, 'original' for me, and I stuck with Wu-Shu (one of Kung-Fu styles - not 'cheesy' at all) with some Wing-Chun (I use that wing-chun dummy for practice). If you want strength, and I mean muscular power - I suggest you consider that fitness kickboxing you mentioned as an option. However, to gain the strength I think you're talking about (will not be gained by Tai Chi), the training must be rigorous, or it'll be like you're on some diet trying to lose weight by raising your legs and moving your arms (LOL like Tae-Bo :=)).
By the way, if it is muscle gain you want, try weight lifting, but if it's strength you want, don't think of Kung-Fu as 'cheesy' - recall Bruce Lee (one of the strongest men alive in his time). Although he called his style Jeet Kune Do, Bruce mastered Wing Chun first and applied those Kung-Fu techniques further on to develop his own style - having the best techniques of many systems and implementing those into his Jeet Kune Do: “To create a method of fighting is pretty much like putting a pound of water into wrapping paper and shaping it. It possesses everything but in itself is possessed by nothing."
'At any given time his art can resemble Thai boxing, wing chung, wrestling, or karate. Its weaponry resembles Filipino escrima and kali (as was shown in the "Hunted"), and, at long range, northern Chinese gung-fu or tae kwon do.' WBB.
And yes, sit in on the class, and if you don't like the class, it doesn't matter that such discipline is not right for you or that you would not succeed at it. Obviously, you cannot make judgement by one class. Aikido is a POWERFUL martial art which requires virtually no strength as it is not based on the practitioner applying it. Karate in this way is sort of like an opposite (and kickboxing is not really a martial art). If you want a religious aspect to the art, Aikido and Kung-Fu (of the ones you mentioned) would be the best picks.
Good luck, and take care ...