@Kay (this does not increase strategic depth) but you could add random events/traps to yout arena; In my game it makes it feel more alive and fun to go around ;)
you could split the map into bioms and give certain stats (+2 stamina for instance) if the players sits in one; You could move the bioms around each turn too :P