I think the first day I got my theremin I tried to (horribly) play the melody of "Ode to Joy", but the first song that I was serious about learning is Saint-Saens' "The Swan".
In hindsight, yes, I guess I'd start with that song again. It's not the easiest song you can play, but I like it. Some easy songs (the "Ode to Joy" itself, for example) are somewhat plain when played on the theremin. "The Swan" is less easy but it's also richer, it teaches you a variety of things (it has some moderately long intervals, but it also has those scales that go up, you can play legato but you have to use the volume loop too, there are sustained notes where you can practice your vibrato and try different frequencies/intensities of it, etc.) and it has a lot of possibilities for expression. Even when you don't play well, it lets you start to see the possibilities of what you are going to be able to do with the theremin, the passages that you get right are very satisfying.
And yes, it's very clichéd, but who cares. When one's learning, originality is not a priority, at least IMHO.
