Here I Stand, although it doesn't have many similarities to the games you've already mentioned.

Struggle of Empires (or Conquest of the Empire) may be a good choice.

Other 4-6 players wargames could be Game of Thrones, Dust or Britannia.

There are some nice card-driven wargames but for 2-5 players: Sword of Rome (with the expansion) or Napoleonic Wars.

Conflict of Heroes: Awakening the Bear! - Russia 1941-1942 apparently plays well with 4 players, but does not play with more.

Shogun might be a good choice for you. It combines the feeling of combat and area control that Risk has with some of the more euro-style feelings you'll get from Puerto Rico and Settlers. It plays up to 5 players, and is a very good game.

Viktory II is the answer.

Also good is Nexus Ops, but only for 4 max.

Wizard Kings will cope with up to 7 players in the basic game, but you'd be advised to get some Wizard Kings - Expansion Maps to give you some room to move around!

Conquest of Paradise can have up to 4 players.

Attila the Hun: The Roman Empire in the East seats 6, and it's western sister game Alaric The Goth: Fall of the Western Roman Empire seats 7... But don't look so good!

Senji is a great Euro style war game that we had a chance to play GenCon 2008, it's best with 4-6 players, but can be played with 3 as well.

Another vote for Here I Stand. Not too hard to figure out, and lots of negotiation, backstabbing, etc.

I second Shogun.

You also might want to check out Diplomacy and Revolution: The Dutch Revolt 1568-1648.

Along the lines of the games you mentioned, there are Dust and Attack! / Attack! Expansion (soon to be republished together as Attack! Deluxe Expansion), all of which support up to 6 players. You might also consider Cosmic Encounter, which is scheduled for republication soon, although with only support for 5 players out of the box.

For games with a bit more bite, I agree with the suggestion of Here I Stand, although I really prefer playing with 3 players instead of 6 because there can be significant down time. I have not played Wizard Kings, but I think it's a good suggestion for a game to try with 6 players. Another to look at is Napoleon's Triumph, in which the multi-player game is handled by assigning leaders to the different players in a hierarchy for priority.

With 4-players, I would recommend Friedrich.

The game is played using an interesting 3-versus-1 game design, where the Prussian/Hanoverian player attempts to fend off all 3 of his/her rivals: Russia/Sweden, Austria/Imperial Army, & France. In game combat revolves around the play of tactical cards (that is, specially printed playing cards in 4 suits) and the hand management of these cards. If you are looking for a different type of wargame, then Friedrich might be the game for you and your group.

Conquest is a great 4-player game (it also has a 2-player version). It's becoming scarcer, with the designer passing away last year. Grand Conquest is an advanced version, adding siege weapons, additional troop types and terrain.

I'm surprised no one has mentioned Conquest of the Empire yet. Seats 6.

A personal favorite of mine is The Succession Wars. Set in the Battletech Universe of 2025, you can play each of the 5 Great Houses of the Inner Sphere, plus a 6th player in control of ComStar (IIRC).

Another favorite, also sci-fi themed, is Stellar Conquest (for 4 players). Not too difficult to find, it's regularly offered up on eBay.

Among older games, there's 4-player goodness in Invasion: America, it's sister game Objective Moscow: the Death of Soviet Communism (both OOP and pricey SPI titles), and Invasion: America's illegitimate child, Fortress America (kin to Axis & Allies; prices fluctuate on this one).

I own both. They're Axis & Allies clones, set in the Roman Empires. Not terrible games, but there are certainly better ones out there.

The only strong points going for them are the relative scarcity of games on the subject, and that the two games can be linked.

A game with a unique diplomatic element:
Line in the Sand: The Battle of Iraq

A game that might not quite qualify as a wargame:
Time Agent

Both of these games have the potential to be an all day affair if players don't agree to play quickly.

Assuming you can find a copy, Dune might be a good fit too.

But I'll second Here I Stand as a good choice.

Oh, and lest I forget, although it's 2-player, Manoeuvre has enough map boards and armies and decks to have up to 8 people playing simultaneously, so you could have mini-tournaments.

Here I Stand is an exceptional game, but it's a huge jump in complexity from the games you're used to.

War and Peace
Empires in Arms (if you've got a spare few months..it's pretty good)
Days of Decision III
A World at War/Advanced Third Reich
World in Flames

These provide some player interaction and deal making on top of being a "conventional" wargame.

Viel Spass

barbarian kingdom & emperor plays 4-6

In rough order of increasing complexity:

Wizard's Quest 2-4, should be available on eBay.
Soldier King 4, is long out of print.
Conquest of Paradise
Shogun
Cosmic Encounter
Soldier Kings 2-8, was just re-printed. (I'd say it's probably best at around 5-6. Need more people to test the theory.)
Successors (3rd Edition) 4, is about to start shipping from GMT

Games not linked have been previously mentioned, and that I also recommend.

Warrior Knights

Twilight Imperium 3rd Edition

With the possible exception of War and Peace, those are all, like Here I Stand, WAY more complex than stuff like Axis & Allies or Risk. Some of those rulebooks are over 100 pages. Which is not to say they aren't good games -- I just think they'd be a bit much for your group at this time.

Friedrich, Game of Thrones, Dune, and Shogun would all be good choices. Empires of the Ancient World and Mare Nostrum are also good, but they have more Euro-y elements to them.

Wings of War - Famous Aces will play up to 4 out of the box; with any one of the expansions, it'll play up to 8. It's not your typical war game but it's World War I aerial warfare with each player controlling a plane. We particularly like facing off with teams of 3 or 4 each. I haven't tried it yet but Wings of War - The Dawn of World War II takes the aerial war to World War II and plays up to 6 out of the box.

Since your group seems to like both types of games (such as Risk and Puerto Rico) you might want to check out Age of Empires III: The Age of Discovery since it has elements somewhat similar to both of those types. It has some Eurogame mechanics (worker placement, special roles, victory points) with a bit of conflict (fighting over colonies) as well. With the bonus set of playing pieces, AoE3 plays up to 6 players and scales fairly well...

Another game that has both elements but leans more heavily towards combat is Galactic Emperor...

Terakh: A Creative Strategy Game plays with that many, lots of fun combat, fairly light game, but you may want my alternate rules posted here on BGG to avoid long waits for players eliminated early.

Shogun has already been recommended but a similar game Wallenstein is another great 5-player "wargamish" game. Especially the dice-tower (or better, the cube-tower) is a great innovation. The rules are easy to digest, the game can be played in 2-3 hours (an evening session) and it offers lots of different strategies. To call it a real wargame...........well no, but on the other hand: it can be as tense as lots of "real" wargames. And it can be very interactive.