If you are using the right weapon then a mage can brawl just as easily.
This is true. I think that this doesn't get stated enough in fact. W/ a crescent weapon, moon weapon, or northern regalia (dragon weapons too early on) a mage can hit extremely hard w/ melee weapons. As such, a mage is still a very viable melee warrior.
I think in general this game's hardest enemies are player sized enemies such as Doran, BP Selen Vineland, and the 5-2 Cleaver phantom.
All of them can be cheesed though.