Personally i use a 32 color Amiga palette (0 to 15 steps) i made some time ago after lots and lots (and lots) of trial and error, and again could be improved to save 1 or 2 colors
http://pixeljoint.com/forum/forum_posts.asp?TID=19759
then i try to restrict if i need 16 colors in this castlevania style game i am drawing (with some touches from master of darkness).