Capital One's card wouldn't be as good an option at smaller (read: higher fare) airports because its "miles" for free travel are based on the price of a ticket and not tied to any frequent-flyer program.

From TYS to YUL, US Airways has the most direct routing, through Pittsburgh, but a quick search on ITA shows their fare to be considerably higher than Delta (via ATL), NW (via DTW), and American (through ORD). However, US Airways does not serve Lubbock. US is a Star Alliance member so you'd also be able to receive credit for Air Canada and United flights.

One thing you might want to consider is the ease of obtaining elite status with one or more airlines. That way you can enjoy priority boarding, free upgrades, and fewer blackout dates for award travel. US Airways' Bank of America Visa card offers automatic triple miles for all tickets booked in the first six months of card membership, which can put you on the fast track to Preferred status. American allows you to complete a "challenge" toward Platinum or Gold status by flying a certain number of miles on qualifying fares in 90 days. (Go to the AA forum and search for "challenge" if you want to find out more). Delta, of course, has gutted its SkyMiles program so that the cheapest fares only earn 50% of miles toward elite status, so if status is important to you avoid DL.

For the city pairs you'll be traveling to most often, AA offers the best service, both through ORD and DFW. If I were you, I'd move most of my flying to American and perhaps choose US Airways/Air Canada/United as a secondary carrier.