How 'bout a Water/Psychic cuttlefish?
http://www.doublepluscool.com/blog/wp-content/uploads/2008/12/cuttlefish1.jpg
From Wiki:
Cuttlefish are marine animals of the order Sepiida. They belong to the class Cephalopoda (which also includes squid, octopuses, and nautiluses). Despite their name, cuttlefish are not fish but molluscs. Recent studies indicate that cuttlefish are among the most intelligent invertebrates. Cuttlefish also have one of the largest brain-to-body size ratios of all invertebrates.
Make its head translucent so it has a visible psychic-inspired brain (I don't know how'd you go about spriting that, though. Maybe with some color-transparency shenanigans...?) Also, the sprites would have them shown in an upright position, so that the brain is easier to discern.
Regular coloration is moderately-dark blue, with lighter blue tentacles and a green brain. (Cuttlefish have bluish-green blood, so I figured the brain color could be a nod to that.)
Shiny coloration would be inspired by this:
http://upload.wikimedia.org/wikipedia/commons/e/e7/Metasepia_pfefferi_1.jpg
because this looks awesome.
First form is Cuttlemind (cuttlefish + mind), who looks basic, as a starter should. It has a small spherical brain, and two large, beady eyes giving an inquisitive stare, indicating its curiosity. Its tentacles haven't grown much yet, and two of them are longer than the rest. The shape of its head is a simple 'tall fin' shape typical of a cuttlefish.
Second form is Membriida (membrane + sepiida, the Order to which the cuttlefish belongs). Membriida's brain has become more elongated than purely spherical like Cuttlemind's, making it a tall cylindrical shape. Membriida's eyes also have a bit of a smug look, as Membriida has become cocky due to its heightened brainpower. Its tentacles have also gotten longer, with the two primary ones still being longer than the rest. Its head has also narrowed to accompany the brain's shape.
Final form is Cephadulla (cephalopod + medulla). Cephadulla's brain has become more spherical once again, but not perfectly so like Cuttlemind. Its eyes have a serene, wizened look, as Cephadulla has gained great knowledge and insight. In its final stage, all of its tentacles are now the same length, contrary to those of a normal cuttlefish. The top of Cephadulla's head, rather than being a single point like a fin, has several small points, making it look like a crown.