I've chosen "talk then roll", but it actually depends on the the skill involved. In advance I'll have to say that I think it's important for immersion and roleplaying that the players play out their dialogues to some degree:
Sense motive is a simple roll. It's easy to figure out why. Sense motive is a thing of good perception and knowledge, mixed with a little empathy. No thinking involved.
Intimidate is simple as well. The player tells how he wants to intimidate the NPC, then the dice is rolled. It's simply a thing of confidence, bearing and body language. Everybody can say "Don't do that or I'll crush your head", but some people get laughed at for it and others are feared.
Bluff is similar. I think Bluff isn't really the skill to come up with a good lie, it's about the ability to not move your eyes the wrong way, keeping your voice streight, that kind of thing. Basically about selfcontrol and confidence. You can try it out against a person that knows how to detect lies, tell them something perfectly plausible and they know from you behavior when you say it that it's a lie (at best as part of a bet, it's easier to tell a lie when nothing depends on it)
Gather information is really hard. The question is if GI is the skill to ask the right questions, ask questions the right way or the skill to look at the right place for answers.
The third way is the easiest skill to roleplay: Grang the Halforc wants to gather informatins (modifier -2): He goes up to the next best peasant that knows nothing (roll of 10-2=8), the is played out. Janus the Bard (modifier +12) wants to know the same thing, he enters the next best Bar, scans the room and spots a person that is likely to know something (roll of 10+12=22), he goes up to him, the rest is diplomacy, a bribe, roleplay, and possibly even bluff and intimidate. Now this would be more of a wisdom or inteligence based skill, it also goes into the area of spot and search.
The two other approaches give us the question: how do we roleplay this encounter? Normal roleplay, followed by a roll is somewhat not very logical, but if you just say what you want to know, roll and get an answer, this isn't very flavorfull.
The gather information skill makes a lot of sense from a design/metagame point of view as a shortcut to get information to the players, however it has no in game reason to exist, as it can easily be covered by roleplaying and the other social skills, it also has the two big drawbacks that it pushs the players to spend some of their precious skillpoints on a skill with little more than use of plot funktionality and a single messed up roll can have the PC's miss important clues or be left stranded with loose end and no idea how to go on.
When I think of gather information in the Sharn campaign I played in, which at some points was very heavy on investigation it shortened some parts of play significantly, but through this took away a lot of possible roleplaying and deeper imersion in the setting, and often got us end up with the mentioned problems.
I feel if the DM thinks a informatio is trivial/easy to optain, he could give it the players without a need to roll, if he thinks a information is to important/hard to optain to just hand it out, the players deserve to work harder for it than one skillcheck, just like any other challenge.
Diplomacy really troubles me to no end. I still don't know what to do with it and often thought about removing it alltogether.
One could treat it like I treat bluff and intimidate: The skill isn't about what you say, but about your body language etc. Now, this shurely part of the diplomacy skill, but I think diplomacy is more than any skill out there about what you say and how well your formulation is.
One way to simulate this is, that you roleplay it normaly, then roll and tell the players how his PC really said it. Now, the pure absurdity of this just feels wrong, and will also make players just parafrase what he wants to say.
This is also the last possible solution to the problem, the player parafrases what he wants to say then rolls, and the DM determines how well it was formulated. Sure this works perfect mechanically, but just isn't immersive at all.
Unless I find a solution soon, I'll propably scratch diplomacy.
On the question of players with higher/lower personal charisma than their PC's, well, I handle them just like players with higher/lower wisdom and intelligence.
Higher mental abilities of the player are his own responsibility. He has to keep himself in check, if he can't the DM may step in sometimes ("Do you think that's apropiate for Nork?"), if they have an idea they just have to get out of their system, they could tell it the player of a PC with higher stats OOG.
Obviously, players with lower abilities can't take that responsibility for themselfes. Here the DM should just more often ask the player "Do you really want to say/do this?", the other players can make advises on plans/dialogues. Players also often have more time to think about their plans/what they say than their PC's would have in game.