Let me also point out that the OP will make Gold fairly quickly if he's flying paid J.

Note that the base miles you get from a CC will carry loyalty points, which will advance your status, and higher status gets more RDM's. Of course there are plenty of people who would say that AA miles are worth slightly less than a bucket of warm spit, but I beg to disagree. (Last night I booked a domestic one-way that was $429 cash for 8500 points, and even if I had taken the less expensive connection I was considering for $290, it's still 3.4 cents per mile.)

I would probably not worry too much about a credit card, although if there's a fee-free card that gets you both loyalty points and 2x on AA purchases, it's probably worth using for your AA flights.

If lounge access is sufficiently important you'll probably have to pony up the $450 for the Citi Executive card.

I don't think there's a Centurion lounge in EWR, and if you're a United flyer I'm guessing that's your "home" airport, however if it's not and lounge access is important, you might still consider Amex Platinum. It has a LOT of features including (I'm referring to the Biz Platinum because that's the one I have):
a) $400 annual credit with Dell
b) Free Clear membership
c) $200 airline fee credit
d) Discounts on tickets on your preferred airline (if you're willing to deal with the agony of dealing with totally incompetent agents if you have to change a flight)
e) 35% rebate if you pay for a flight with points.
f) 5x points on flights

Yes it's $695 a year but if I had a choice between $450 for Admirals Club access and $695 for Amex Biz Platinum it would be a no-brainer for Amex.