I experienced your problem of lag in Angry Birds on my HTC Magic for a very long time too...
I solved almost everything with this version of Angry Birds I downloaded from XDA some time ago (sorry but i don't remember the thread right now).
I'll share the apk via my dropbox, you can get it here
Don't know if it may help, but my phone specs are stated in my signature below.
Try it and tell me if it works for you.