|Keep It Simple, Stupid|
<usability hat again...>
Front-door pages can be annoying, but this is where they become useful. A user can select the language initially, then you can set the cookie to remember this for again or the user can bookmark the page with the language they want.
This is certainly one way of doing it, but make sure that you have some sort of 'change language' link on every page. Users can (and do) change their minds during a session, and you can find your way to URLs from many places :-)
Also, make sure that the options you supply are languages (French, English, etc.), rather than countries (France, UK, USA, etc) or flags (Tri-colour, Union Jack, Stars and Stripes, etc.) - since there isn't a one-to-one mapping between languages and countries/flags.
<quick change to IA hat...>
As robot_tourist says, different URLs are a must.
If you have the URL serve up different languages depending on the users preferences it can play merry hell with caches, proxies & search engines.
<off to find my chef's hat - time for dinner! >