I would suggest Persona 4 or the PSP version of Persona 3. That way, you won't run into any bad combat design.
Despite what some others have written in this thread, P3 does not have the better story. There are so many bizarre anime tropes jammed into the otherwise realistic setting, and it can't all fit. The ending is a lot stronger and the story is more "whole", yes, but everything else was done better by P4 and with far less nonsense.
Don't get me wrong, P3 is a fantastic game. I even love some of the parts that make no sense (Aigis~), it's just that they somehow got a couple of boring eccentricities mixed in with the interesting ones. This was less of a problem in P4, which very rarely sacrificed its realism. Because the other world and the Velvet Room play by their own rules, we don't expect them or the things that come out of them to behave normally. The only thing that really strains your suspension of disbelief is the "ALL YO' YENS" fox.
I feel this strengthens the supernatural elements of the game. It makes them feel like something grand and unexpected, rather than just being a hassle or a challenge. There's a reason so much weird fiction relies on the main characters being the only people who know the truth or being the only people to witness something horrifying. When it's common knowledge that YOG-SOTHOTH IS THE GATE!!11, it becomes mundane.
But you should still definitely play P3. My criticism does not take away from the fact that the game and its story are fucking awesome. It also has Aigis and Elizabeth. This won't mean anything to you until you play the game, but you'll come to realize that it is a very convincing argument in its favor.