Well, my game recommendation may seem out of place, but if you look for building&fighting strategy game that is very easy to learn and awfully hard to master, try GO (baduk/weiqi/igo).

And you play using a nice physical goban, the UX is really hard to beat.