I think we've all forgotten one thing here: the restaurant itself.

What I (or, more likely, my partner, since she's more decisive in these situations) would do would be to hail a waiter and ask them to ask the person/people to move. Especially in the cases you state, Dignan, the restaurant has an interest in getting as many people to eat (and pay) as possible. They're going to be a lot more diplomatic and yet forceful about it. They're also the ones in authority - the person can't really refuse a staff member asking them to move, whereas they can refuse you. And it's also hard for the staff member to come back to you and say "Sorry, but the ignorant boor over there doesn't want to move". If necessary the staff can sweeten the deal for the other person/people, knowing that they'll get more money in the long run.

And if you're in the USA, tip the waiter a bit more afterward to show that you appreciate it.

Have fun,

Paul