There are many ways( I'm amking a AOS map too) you can use custom font, tiles, models/skins. But this is just all too common, I recommend custom user interface, font, and minimap image,and a diffrent concept from all the others( like mine is"when blood elves seek what is there:there is war) you probaly want something like see wars AOS where you can choose between naga and the sinisyter murlocs( there are lots of cool murloc skins)
And also a very important factor is the map, maybe make something very diffrent like a hell VS heaven terrain, or under the sea terrain, there are many factors that include uniqueness