I personally like the Steelwing (15 HD) from the Monster Manual 5. It has a lot of really cool attacks and it can fly. You can turn into a 19 HD version, thus making it more powerful.

Also, ask your DM if you are allowed to turn into monsters with templates.

Then you could turn into a Paragon Cryo Hydra. Fun times.