Don't forget GPick as a reference application (
http://code.google.com/p/gpick/):
* Color scheme generation (complementary, split complementary, triadic, square, etc)
* LAB and linear RGB gradienting (these give a much more reliable and balanced result than normal RGB, HSL, or HSV)
* Edit /adjust colors in LAB (gives a more consistent control over brightness and chromaticity)
* DnD of colors, including multiple-at-once; Ability to either move or copy during DnD, according to whether Shift is held down or not
* 7-slot hexagonal-tiled colors display, for visual comparison
* preview gradients (with 3 'endpoint' colors) before adding one or all of the generated colors to the palette. (see the "Blend colors" tool, if you can get GPick 0.24 for your platform)
These are the functions I get a lot of use out of. Also GPick's "Variations" tool is a good example of what you're talking about in the OP ("you would choose a colour, and it would show you the colour plus a couple of shades lighter, darker, redder, bluer and greener")
I'd be intrigued to see how you solve the 'shaped-palette' problem. I've worked on it myself and so far hold the position that it makes the GUI a lot more complex. I'd love to be proved wrong though, cause I prefer shaped palettes myself.
EDIT: I've put my work-in-progress guide to GPick up at
https://sites.google.com/site/davidgowersmiscstuff/gpick-guideEverything except the images were preserved when I pasted it in.