There are plenty of good games that dont give all that much choice to player. Which is why I dont like the "A game is a series of interesting choices." framing. It is true only if you limit definition of games to rpgs or strain definition of "choice" to pretty much anything.

Whether games have great characters is of course subjective, but I have to say that I did not seen them. The best ones tend to be comparable with average book character. (Which is ok, I don't play games for writing, I play them for playing.)