Try and figure out who your visitors are. They tech folks? Wide and you'll be fine. Are your visitors people in offices? Aim for 800 to 1000. It a site for old people or very young people? Then 800 tops.
Yeah it usually depends on the client, however if you use an 800px width on your design and someone is viewing on an 800 x 600 resolution, they will have a dirty scroll bar at the bottom of their browsers because of the scrollbar on the right in the browser window. So we would normally use a width of 780px as default and then increase it as the client needs.
Thankfully though 800 x 600 resolutions are fewer and farther between
Jesus lads! Have a relax... To start with I AM NOT A DESIGNER.. i am a .NET developer. However to justify myself to this crap... Some of the clients we deal with have their own in house designers that are used for promotional work, etc.. so when they get their nose in. Yes it does lend itself down to a client.
Also we have other clients that after a design is done they complain that a 780 width is not giving them what they want.. they would like to see a larger layout. So yes in some cases it does depend on the client.
effect: That is how on earth it depends on the client.. A client isn't going to fork over a serious chunk of cash for a web site that isn't what they are happy with. Yes we can guide them, and suggest.. but at the end of the day.. THEY are paying YOU .. not the other way around.
Anyway, we have all had clients i'm sure, who want X and will not be swayed. But a lot of a designers job, as tomed says is to educate the client as to why X is not a great idea, and Y may suit them better.
You need to backup all your decisions regarding design with facts, and reasons as to why you chose that route, you are meant to be the expert in the field, and should act like that.
If you blindly say 'yes' to everything the client asks for, you are doing them a disservice.