It depends where your game development strengths are. If you are good at graphics programming then show some cool effect. If you are into AI then maybe some kind of multi agent pathfinding system.
I think that what the guy is telling you is that whilst writing a full game is an excellent achievment it isn't always the best example to gauge somebodies programming style. He just wants to see a small demo program that shows off how good your code is but without being too trivial or too complex.

If you are landing a job in the game industry, and the company tells you to write a well-structured code with good style, what would you do to impress them?

They don't expect to be impressed.

They want to see that you can code. That is all.

They're generally looking for a few pages worth of code, maybe 400-1000 lines as an excerpt from a larger system.

It should be something that demonstrates you have a good understanding of programming. For example, you might give code that builds up and maintains a hierarchy of data when a standard container wouldn't work. You might have some processing tasks that you are comfortable with. It should include a few algorithms and a few data structures.

In a pinch, implement a few common algorithms that are not already part of the standard library, roughly 500-1000 lines of code. Double-check that they run okay and have their obvious bugs taken care of.

Keep in mind that in all aspects of interviewing, every step is designed to EXCLUDE, not to include. They are looking for reasons to reject everyone from the pool until the pool drops to 1. So make sure your code works, make sure it does what it says it does, make sure you can explain it, make sure every word is spelled correctly, make sure it compiles cleanly even on high warning levels. Then keep it short and simple, enough to convince them you can code reasonably well, not enough that they can scour it for obscure errors.