I'm open to anything, including card based games with no board I guess
I honestly can't tell if you're trolling or not.
I'll give you the benefit of the doubt and suggest you check out a game called Dominion.
It's possible that he came in via the boardgamestrategy.net page (or one of the other sites), in which case it's quite possible he hasn't heard of Dominion. Although he would then have to scroll past the entire Dominion section of the forum to reach the "Other Board Games" area.
Actually, I simply googled "board games" and looked for a well-visited forum that seemed to be populated with serious gamers. After about a dozen links I decided on this forum without even looking up what Dominion was. I figured you'd say if you thought Dominion might match my tastes.
Actually, Dominion might not work so well just going by the games you've mentioned.
For something sort of like Axis & Allies, you could consider
Kemet, which is a nice, action-packed dudes-on-a-map war game with an Egyptian mythology theme and lots of special powers. For a more abstracted but also more accessible game,
Small World could be what you need. This is more of an area control game than a war game though.
For something like the Dungeon Fantasy Board Game... well, I don't know much about it. It's like D&D in board game form? I've been really interested in
Assault on Doomrock which currently has a
kickstarter campaign for an expansion. The combined pledge actually looks like a good deal; I personally haven't committed because I don't know how much I would get to play it simply due to its length. If that's not a problem for you though, it sounds perfect. You could also look into the
Pathfinder Adventure Card Game. I could give more specific recommendations if you elaborate on what you like about the Dungeon Fantasy Board Game.
Stratego has a lot of hidden information and bluffing, right? You could try something like
Specter Ops,
Letters from Whitechapel or
Scotland Yard where a team of players is trying to hunt down one solo player with hidden movement. Or you could cut out the board stuff and try something like
The Resistance,
Coup or
Ultimate Werewolf.
I don't know what this Treasure Hunt game is; BGG has several games by that name. If you describe how it works, I could make suggestions based on that too.