And I'm put in mind of this gadget, which I was introduced to some months ago and keep meaning to get -- basically a motion-sensitive magic wand with an RF transmitter, which you can program to use as a TV remote.
And now I'm thinking: put them together, and you might really have something. I'm envisioning a wand similar to this, but more powerful. It would probably have a Bluetooth transmitter for talking to the Google TV box, maybe some Wii-style positioning systems, and would contain a small condenser mic. Along with the usual motions, you can hold the thing up in front of you, which activates the mic and lets you send voice commands.
That might work quite nicely. Define how to navigate the UI with the wand, using flicks and "presses". Use voice input for search. It would take some testing and refinement, but I'd bet that you could produce a gadget that is decently easy to learn, intuitive to operate once you've learned it, and hellaciously fun...