Well, a large tileset could be just a matter of resizing a small tileset, right?
As for backgrounds... I'm not really sure I understand what the trouble is here, but here's some facts just in case:
If memory serves me right, on the map display, the background colour is only used to represent:
(for creatures)
Lying down on the ground (brown) - could be replaced with rotating the tile by 90degrees (though in that case it will be important to keep all creatures facing one direction so that they will all be rotated to be lying on their backs)
Flashing Blue background + grayscale tile (legendary) - with larger tiles- just making the dude flash to gray or maybe gold would be enough
Blue background + colours shifted to blue (underwater) - same as above, this will work very well with the actual tile rendered.
(for items): basically the colour depicts a puddle the item is lying in. Also irrelevant if the actual tile is depicted.
(and for walls): the fact that it's a wall

(this is circumvented in a "graphic" tileset, while not a problem in an ASCII tileset).
As for the fun with transparency and blending... I, for one, am abandoning it, because so much new stuff is added that is using already used tiles, that making appropriate symbols is getting impossible. So the tileset I'm using now is
http://mayday.w.staszic.waw.pl/~mayday/upload/4%20lxnt/mayday2.pngOnly the wall tiles have been heavily edited to depict something more... blockish.
Anyway, there's a 21x21px set I've uploaded some time ago (this the maximum tileset size my display supports)- plenty of space in the creature graphics, as many of them are just reused 16px icons
http://mayday.w.staszic.waw.pl/~mayday/upload/21pxDFG.zipthe tileset in this one uses the "graphic" approach
http://mayday.w.staszic.waw.pl/~mayday/upload/4%20lxnt/mayday21.pngOr maybe you mean that the problem is the semi-transparent backrounds in many tiles? If so, I can remove them for testing.
Regarding mood icons- would you be able to display some graphics partially outside of the tile? Like a comic thought baloon centered in one of the upper corners of the actual creature tile?