Moat. Moats are cool.
Watchtowers. Usually at the corners, but, hey, depends on what you're watching for, right? Might there be scrying rooms? (Always more than one floor.)
Throne room. Throne room should establish philosophical relationship between lord and subjects. May double as dining hall, depending... Path from front gate to throne room is usually direct.
(In general, palaces have "public" sections--throne room, receiving rooms, consultation chambers, and "private" sections-living quarters.)
Windows. Windows in palaces generally have views that are beautiful, strategically significant, or both.
Kitchen. Should be one of the most detailed locations. Food defines cultures as different.
Monarch/lord's sleeping quarters. Insert monarchical weirdness here.
Sleeping quarters for whoever else lives there. Consorts, advisors. Make not-boring or elide.
Records and documents archive. (Can be folded in with library if boring.)
Art (everywhere). Art is always evil or cursed or alive.
Place for the education of the lord/monarch's children.
(Zoo?)(Hunting grounds?)(If palace is abandoned then what's in it might be descended from hunting or hunted animals.)
Armory. (Weird and obscure guards.)
Place where they keep other supplies like lamp oil, etc.
Harem. (Traditionally, harems are self-sufficient--have own chapel, etc..)
War room/situation room. (May contain awesome map.)
Consultation chamber--mirror mirror on the wall, etc.
Workshop--when stuff needs to get made they go here. Has tools and stuff like that.
Stables. (Find way to make un-boring)
Place (balcony, generally) to stand and address subjects.
Well/cistern/aquaduct. Anything could be down there. Wells are cool.
Symbolic architectural features with traditional "powers" attached--Gate of Inexplicable Destiny, Widow's Window, etc.