It would be very helpful to better understand your goals. Which is your priority? Domestic or that trip to Paris/Rome? Obviously Southwest works for domestic travel but they won't help you get to Paris. As to Paris/Rome, how many will be traveling and what fare class (economy, business, first) are you hoping for? How long do you hope to stay and any hotel preferences?

Also, do you currently have any points in any program(s) and, if so, how many do you already have?

With this in mind it's easier to suggest a credit card strategy more tailored to your needs.