For example, in my games I use streetwise to monster info checks against civilized races in most cases... always kind of bugged me that you're supposed to do a nature check to find out about pirates. Streetwise is also more likely to help you size up an individual "can we take him?" "roll streetwise" "17" "It'll be a tough fight, but yeah. Watch out for higher damage when he's bloodied."
History is a good skill for determining enemy battle tactics. "What's their plan?" "Roll history" "13" "These guys are likely to attempt to flank somebody, but you aren't sure who they'll go for." "Support with insight?" "Roll it" "24!" "They'll be flanking your fighter. Once he's tied up the rest will probably try to take out the mage."
In battle intimidate as a minor action can cause enemys to change their tactics, generally to pick a target other than the intimidating one. Diplomacy is like the opposite of the RAW use of intimidate: it it looks like the battle is going poorly, negotiate terms of surrender. Combine with bluffing for excellent results.
How do you guys get the most out of underused skills?
I was thinking about using streetwise for civilized humanoids as well, history for cultural knowledge,
Underused skills? No, I really don't know what else to allow Acrobatics and Endurance to do...
It sounds like the OP is combat-heavy. Those underused skills are the main skills for many non-combat encounters. Although, many also have use in a dugeon.
Streetwise can be the absolute best skill in the game in an urban campaign. I recently DMed a few levels of a heroic campaign where the PCs were all members of the city watch investigating a murder which lead them deep into the bowels of the underworld and got them involved in crime syndicate intrigue. Virtually every sessions saw serious use of streetwise. On the other hand, if you're in a dungeon or the wilderness its useless, so it really depends on whether your DM is taking more inspiration from Tolkein and other questing high fantasy, or from stuff like Terry Pratchett's Discworld or China Mieville's Bas Lag books where most of the action takes place in urban settings. Or, if you want to put it in D&d campaign terms, streetwise is awesome in eberron campaigns especially if they take place in sharn, but can be all but useless in a forgotten realms campaign not set in waterdeep or baldur's gate. It is entirely dm dependant, so before training it I'd ask your dm if he has a rough sense of what sort of settings you'll mostly be playing in.
Acrobatics is entirely dependant on how varied the battefields you play in tend to be. If your just going through processions of flat, circular rooms, its useless. But if the dm goes out of his way to make a really interesting room with perhaps multiple levels, things to swing on or climb up, etc. Then a player who gets creative with acrobatics can really improve their mobility in some interesting ways. I was once in a fight that took place in the engine room inside a giant mechanical construct based on the tarrasque, and our rogue was having a blast swinging from chain to chain to easily move around the battle.
I am stealing that "history roll for tactics" idea. Usually I would have just gone with insight, but using the PC's knowledge of the way a being fights is great. I would probably also supplement this idea with Monster Knowledge rolls (i.e. Arcana for Fey, Shadow & Elemental, etc) to get a better fix on what these monsters do, and possibly hold off on History for more civilized beings.
be careful not to step on the toes of the new skill powers...
Tactician's measures - History utility level 10
Thievery to gain clues on traps and other mechanical mechanisms - a bit like how Knowledge skills are used to identify monsters.
I also tend to use History to remember cultural tidbits about the more common monsters, while the Arcana, Relgion and Nature check are more about the biology of those monsters.
I'm stealing this OP.. I just want you to know that.
be careful not to step on the toes of the new skill powers...
Tactician's measures - History utility level 10
Until the PHB3 is out, I won't worry about those. Cause you know, some people don't use the DDi stuff. . . 
Thievery to gain clues on traps and other mechanical mechanisms - a bit like how Knowledge skills are used to identify monsters.
I tend to use dungeoneering for this, since thievery is already very useful for traps (and in general)
I have moved this thread based on a VCL request. 