If it is your first credit card, go for as small a credit limit as you think appropriate. And then ensure you pay off the full balance each month. I started off with a $500 limit, then increased it to $1000. It made it really hard to get in trouble.
You are likely to pay higher annual fees for cards with better options. Some banks will waive the annual fee if you keep your chequing account's balance high enough. In my case, the savings in annual fees more than made up for the opportunity cost in 'locking away' some cash in my chequing account.
The specific card that makes the most sense will very much depend on your needs. I went with a card that offered free extended warranty on purchases, cash back, and free insurance on car rentals. You say that the travel rewards aren't likely a great deal for you, but if they are, you tend to get more value out of a travel rewards card than the equivalent cash on a cash-back card.
My bank was very happy to discuss my credit card options, taking into account exactly what I wanted. You may want to set up an appointment with your bank/credit union.
My preference is to get the credit card from the same place I do the rest of my banking, though this is mostly out of convenience; it's easier for me to pay off my balance, which I do on a weekly instead of a monthly basis.