Despite being a media pariah on this issue, go with Southwest. Their "customer of size" policy is very fair and well spelled out. Purchase two seats. Pay for their early bird check-in or even business select to get on the plane within the first group of passengers. With their open seating/no assigned seat policy, choose a pair of seats and enjoy your first flight. Southwest flies 737s across their entire fleet so there is no chance of ending up on a small regional jet. If the flight is not full, you will receive a refund on the 2nd seat purchased.