I just got a great idea! We can make 2 sprites for every enemy, legendary, and hero. We would make a overworld sprite which would be 16x16 and a battle sprite that would be 32x32. Legendaries would also have a 32x32 sprite for battle but have something special about them so you know that they are legendaries.