Card games with traditional decks of cards mostly fall into either trick-taking games (Whist-family games like Bridge, Pinochle, Euchre, Spades, or Hearts) and melding games (Rummy-family games like Gin, Go Fish, or Canasta). There are exceptions, but they are less well known and will likely not meet the accessibility criteria because of the learning curve.
In general, from my experience trick taking games are quicker to learn and play faster, and strategy is largely confined to individual hands (although your success in each hand will affect how you play the next). The king of trick-taking games is Bridge, and for the devoted student will be very rewarding, but learning the subtleties of bidding and play can be daunting, and expert play requires a partner that you have practiced with. Spades is more approachable to the beginner, has a fair amount of team strategy, and as has been noted has the potentially thrilling and aggressive play.
Melding games are equally varied in style, but in general tend "feel" longer and more strategic. My personal favorite is Canasta, popular enough in the 50s to challenge Bridge for the most popular four-handed game. Played with two decks of cards it has many strategic options around when to go out, what styles of melds to make, and taking the entire discard pile (risky, but potentially very lucrative!) On the other end of the spectrum is Cribbage, which is a fast-playing melding game which can be played either four- or (more commonly) two-handed. Not a lot of strategy across hands, and a fair amount of luck, but quick to learn and has some interesting strategic choices as well.
Ultimately, you will not find games with traditional packs of cards to be as deeply strategic as a game like Dominion, simply because there is less variability in play, and early missteps are less likely to punish you in the end-game. If you want to find card-based games that are interesting yet approachable, I recommend looking at a number of custom card games such as Fluxx, Bottle Imp, Citadel, or Innovation (a new game for 2010 that's garnering a lot of praise).