Bosses that resist magic might be interesting. Certainly will stop the BLM Burn Mania ^.^; I always thought the idea of a boss that would 'cycle' through weaknesses would be nice (sometimes weak to magic, melee, piercing, etc.) or have adds that had different resistances.
If we had a simple situation:
Boss weak to melee
Half adds weak to magic
Half adds weak to piercing
Would certainly encourage more diversity.
