You don't have to package all of the Blender executable files, but you do have to include a Python distribution and some associated DLL files (on Windows; not sure about Mac or Linux). EDIT: Come to think of it, if you don't use any Python, maybe you don't have to include the Python distro.
The player's 11 MB, but with the DLL files and such it goes up to around 32 MB or so. That's not that bad, though, considering average Internet download speeds (32 MB = an hour on a bad connection nowadays), and what the BGE's capable of, graphically (
Dead Cyborg was a game made with the BGE).
Also, you can hack away some of the Python distribution that you don't need (socket, e-mail, html, http, etc) for less size. A recent test I had with no size optimization was around 70 MB, but I also had sounds and a 10 MB wave file BGM song. :I
EDIT: I should make a smaller Python library for distribution for usual applications in the BGE (i.e. no excess Python libraries).