I recently got phenomenally lucky in a game and ended up with rings of polymorph and polymorph control early in the game, and have the following comments/additions/changes.
First, a general comment. I find speed to be incredibly important to keep track of. A titan, at base speed 18, is 3 times as fast as an umber hulk, at speed 6. Know the speed of what you poly into. If you are fast, add 1/3, if you are very fast, add 2/3. The speed is how many "movement points" you get each time tick. Each time you take a basic action (move one square, initiate a melee attack, etc), you burn 12 "movement points". So a very fast titan gets 2.5 actions every time tick. 2
(I haven't looked to see whether magic resistance %ages actually affect players poly'd into monsters. In case they do, I'm mentioning them below...)
Now for some specifics. Early on, winged gargoyles are pretty sweet. They have a better base speed than player races (15 speed instead of 12), awesome base AC (-2), very nice attacks for their level (3d6 weapon/claw, 3d6 claw(/weapon?), 3d4 bite), they are stoning resistant, they have nice strength (18/**), they fly (so no falling in pits, no falling when going down stairs burdened, can cross water, can pick stuff up off the floor, won't break potions when you drop them), they are not super-duper high level (9 hit dice), so your polymorph will last a while, and if female, they can lay eggs, so you can produce some pets that are quite nice in the early game. The pets will be gargoyles. Up sides: very nice AC (-4 base and they will pick up and put on armor - I had a couple of gargoyles that ended up around -13); stoning resistant; won't eat corpses, so more food for you; decent attacks (2d6 claw/2d6 claw/2d4 bite - not sure if they will use weapons given the chance). Down sides: they are slowish (speed 10), especially if you are cruising along as a winged gargoyle, even more so if you have inherent speed and no way to get them fast; because they don't eat, it's theoretically easier for them to become untame, since you may not be able to increase their tameness 3 (Although I've been too chicken to leave them on a different floor long enough to see whether this is actually a problem, and I've tried pretty hard not to do other bad stuff, like displace them into traps. On the flipside, because they don't eat, my understanding is that leaving them on another floor will at worst make them go from tame to peaceful, rather than ever resulting in them going hostile.); they don't fly, so unlike you (again, if you are cruising around as a winged gargoyle), they can fall into pits and stuff. If you poly into a winged gargoyle, your wings will break your shirt, body armor, and cloak. Because of this, it's also worth considering polying into a plain gargoyle if you like your armor and get a controlled poly forced on you. No flying, no laying eggs, and slow, but you won't break your armor, your ac becomes very nice, you get extra attacks, and you are immune to stoning.
Another interesting early choice is marilith. 6 attacks (2d4 weapon (x2), 2d4 claw (x4)) is insanely nice early in the game. If you fight bare-handed you have a chance of summoning "hell-p", which means another marilith (maybe more? it only happened to me once and I got 1). A marilith pet does a lot of damage for as low level as they are (7 hit dice); has a very nice ac (-6 base); ok speed (12); nice magic resistance (80), although I think this might make it harder to make them fast or invisible; nice resistances (fire, poison); sees invisible; will use weapons; and they don't eat (see above for why this might be a mixed blessing). The extra limbs will break out of shirt, body armor, cloak.
I found that when I got hungry and there was a lot of junk armor lying around, Xorn was a reasonable choice, since they get nutrition from eating metal objects. They phase through rock, so you can pass through walls as though they were not there, but will not leave a path that non-phasing creatures can follow. Phasing is handy for avoiding confrontation and picking up gold and gems stuck in walls or vaults. If you don't have a way to poly again, be careful about getting stuck in a wall when you change back to normal form. I think praying will get you out if you are able to pray. Xorns are slow (9 movement) and you will break shirt, body armor, and cloak if you poly into one, but they have ok attacks (1d3 claw x3, 4d6 bite), nice ac (-2 base), some magic resistance (20%) and they resist fire, cold, and petrification. lots of folks poly into xorns to eat metallic rings and amulets, but I haven't had a good opportunity to do this yet, you should make sure you get the intrinsic you think you will get before eating a useful ring like free action, and the chance of getting the intrinsic is like 1/3 or something. Xorns have 8 hit dice.
Dragons are okay. 15 hit dice, ac -1, speed 9, magic resistance 20%, damage 1d4 claw x2, 3d8 bite, flying. you can also use #monster for a 4d6 breath weapon which uses 15 magic points. The downsides are pretty big: no hands, so you can't open or close doors, wield weapons, or manipulate things (so you can't put things into or take them out of bags, for example! you don't want to be hungry and a dragon with your only food inside your bag of holding); wrong body shape to wear any armor; slow speed. Changing into one will break shirt, body armor except for dragon scale (which might need to be the same type as the dragon you are changing into, but I'm not sure if it's possible to wear one type of dragon scale and even try to poly into a different type of dragon), and cloak. However, the big payoff in my opinion is that if you are a female dragon, you can lay dragon eggs. If you carry them, they will hatch in a while and you will get pet baby dragons. These will be 12 hit dice, ac 2, speed 9, 10% magic resistance, attacks: 2d6 bite, and they fly, but they do not have the resistances of full dragons and they will not drop dragon scales if they die. If you keep these pets alive until they get 15 hit dice (above 112 hit points, I think), they will become adults and get all the perks. As for dragon type, magic resistance is really about the most important resistance, so gray dragon is decent. Lately, I've been more inclined to wish for a magic resistance artifact as early as possible and try to get silver dragon scale mail by some means. Also, silver dragons are more resilient pets, so I've been going with silver a lot. Yellow dragon is potentially interesting since they are petrification resistant (maybe the only potential mount that is?), as well as being acid resistant (although this may allow them to eat acidic corpses, which maybe you'd rather eat... I haven't looked to see which acidic corpses are attractive to carnivores).
Titans are really nice once you are high enough level that the poly will last a while. They have 16 hit dice, -3 ac, 70% magic resistance, only 1 attack for 2d8 or weapon damage (plus a spell, but you don't get that one). They have infravision and can squeeze past boulders, but I think the biggest advantages they have are flying and 18 speed. They also have 18/** strength. They are large, so you will break shirt, body armor, and cloak if you poly into one, and you will be too big to wear body armor (haven't tried shirt or cloak yet).
Pets I've liked:
1 - http://www.steelypips.org/nethack/343/rint-343.html#poly
2 - http://nethack.wikia.com/wiki/Speed
3 - http://www.statslab.cam.ac.uk/~eva/nethack/pets2.html