Discover is seeing less and less acceptance, so I would avoid it for the network. Capital One has poor rewards and awful customer service. For the first, I would start with something you can build into a card that you will have a long time. Thats why my first was a Bank of America Secured Alaska Airlines card. After 12 months they unsecured and then I requested a CLI from $500 to $2500. This past September I converted it to the Virgin Atlantic World Elite MC and got a CLI to $5000 (along with 65k Virgin Miles that I converted to 130,000 HHonors points
)
As opposed to starting with a card you'll later want to cancel, thus hurting your average age of accounts, one of the primary factors of FICO scores.