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.
Don't get me wrong, primary language guess might be useful, but do make it easy to switch. An easier way might even be to have different domains e.g. de.foo.com or uk.foo.com or even easier: use www.foo.com/uk or www.foo.com/de.
How can you feel when you're made of steel? I am made of steel. I am the Robot Tourist. Robot Tourist, by Ten Benson