Typical "hi-poly" characters in games - that can have facial expressions or whatever - are around or over 5000 polys (like Max Payne (2), Lara Croft in Tomb Raider- Angel of Darkness), and the UV maps are larger around the head or any part that should be higher detail, than other parts of the body.

As for "how high" a polycount you could have - if your levels are that simple, with relatively little action, I don't see why you couldn't get up around 7500 or 10000 - but I'd say use LOD also.

Another way to add high detail is to use photographic textures (www.3D.sk has 1000's) - a high-poly character isn't going to look like much without great texture work.

(for example, the "outdoor" project I'm working on now has this character - 982 polys and one 512x512 texture, based on edited photos - it looks pretty good for less than 1000 polys, because of the texture, so imagine what you could do with more polys, if you have great textures to go with it)