Catan should be at your local Target.
You need to look at what kinds of games you and your wife like. There are several distinct sections of boardgaming and sometimes it is hard to cross over them. The main four you will see are:
Collectable - Magic the Gathering, Mage Knight, Pokemon TCG, etc
European - Settlers of Catan, Carrasone, Power Gird, Ticket to Ride, Agricola
American - Axis and Allies, Civilization, Dune, Fury of Dracula, War of the Ring
Wargames - Squad Leader, Conflict of Heroes, A House Divided, Ogre
There are games that fall out of these sections, like most dexterity games, but the bulk of games fall into one or two of these four styles. But there are reasons for these sections.
Collectable games are usually expansions based, made to travel and fit several matches in an hour or so. They are typically tactical in nature, either card or miniature based. Magic is the penultimate example, but there are literally thousands of collectable games out there. Some have set expansions some are random. Instead of going easy and using magic, I am going to use a defunct one - Pirates of the Spanish Main:

Ships were sold in booster packs, they are small sheets of styrofoam that you popout and then assemble. Games were playable in a small area and there were thousands of combinations to play with. And like most out of print collectables, for $50 you can buy someones collection and have a solid bit of gaming time with it.
European games are typically not confrontation based, combat is rare. Randomness is typically mitigated by external factors, theme is usually in the forefront (though not alawys tied to the game mechanics), and components are often made of wood over plastic. Some are multiplayer solitare, where you are vying for victory points while you build a farm or abbey, others are about racing boats/balloons/dogsleds/etc. Catan is an easy example:

It is all about building a small empire peacefully. The worst conflict you will have is moving a robber onto the opponents area, or blocking them with a road. Winner is the one with the most victory points at the end.
American games are often called Ameritrash. They feature confrontation, heavy combat, randomness, plastic pieces, and dripping with theme that is often tied to direct mechanics. For a perfect example, I will use a game that most of us will never own again - Fireball Island:

You are explorers on an island watched over by a giant totem of a native god. You move based on rolling dice and when you stop you draw a card. The cards may let you move forward faster, or it may cause the god to shoot a fireball down the board at you, knocking everyone on the path out of the way. This is a 3d board, lots of specific to the game pieces, all made of plastic, and heavily luck driven. It is an American styled game to the tee.
Wargames are what real men play. When you want to recreate a battle at the squad or infantry level, that is what a wargame is for. The game design has changed minimally since 1960, the art style is typically NATO based, tactics will win, no plastic or wood all pieces are cardboard chits, get used to reading rules in the standard X.X.XX format, Conflict Result Tables remove luck, and your average opponent will be your fathers age. I use to think I was a grognard (it is the title for wargamers, it is french for "a soldier of the old guard") since I loved a couple of them - Panzer Leader and Ogre specifically, then I met a guy who played the Europa series only. Anyone who plays a monster wargame made of the entire Europa series, where turns are typically four to six hours
per side, is too hardcore for me. the map ends up looking like this:

Now all that said, there are games that cross between the two sections. Like Heroscape, now somewhat rereleased as Magic: Arena of the Planeswalkers, is a collectable American game. And there are other games that defy everything, like Loopin Louie/Chewie. But if you can figure out what style game works for you and your gaming group, you will have a much easier time finding new games.
Personally I am a hardcore American player. I like dice, I like plastic pieces I can paint, and above all I like stories. My wife tolerates these things, but hates playing direct conflict and loves playing coop. I ran boardgaming for a couple conventions for three years and ended up with a collection of several hundred titles, but have paired it down to a few that my wife and I love. Right now we cycle between Planeswalkers, Ogre, Mississippi Queen, and Carroms. But we will be bringing out longer games for the winter months, I foresee Defenders of the Realm getting alot of play.
Once you figure out what kinds of games you and your wife like, you can move up from there. Since she does not like conflict, most American will be right out. But there are plenty of great Euros. What kind of videogames do yall like to play?
All images borrowed from Board Game Geek.