Brutals are easy to finish, but hard to find >.>
Just make a criss-cross pattern and you'll find every worm with at least a minute to spare. (Use a spin weapon to kill the worms faster, and so they can't bite you back and waste your time. Leuc works good on them, also.. maybe even better than Gov.) Other than that, bile everything else if you can, and you're set to go, and can finish them easily with two minutes or more to spare (depending on your damage). Oh, and for those pesky snakes... use firebolt or icestorm to kill them, or if you want that tiny bit of phys exp (i get like 7....), use the spell sense monster, you'll see shadows where they are hiding.
As for leveling... I got to lv 8 on bomies and wolves alone, so yea.... I don't recommend that too much. Kill the biggest things you can at your level, and as always, hang out in the dungeons. They are like a perpetual lv3 map, and you get loot, too.. even the occasional map, so its well worth it. Kill lords whenever you see them (as long as they aren't someone's pets.. grr @ becan), and for all you phys-only people out there, use magic to weaken them if necessary, it isn't below you.
Immense maps can be tough for anyone, even mages. Sure, magic rings greatly lessen the damage taken from spells, but when you can't outrun them anymore, its kinda pointless. Orating to things helps, as does stealing from lords and rexes. A good way to level quickly (though rather expensive) is to convince a sabretooth tiger and a few panthers to be your followers on a Grammar, abrutal and go after some worms.. you level very quickly, though its very costly. (you can only get two-three worms per brutal, more if you're lucky).
Pad your experience as much as you can. By this I mean orate to your prey first to get a little bit of personality exp, then steal from it a few times, then finally kill it with whatever. That way you get exp three times from the same monster. If you're busy doing something else and still want to level personality or magic, nab a few rexes in the dungeon (4-5 or so) with oratory or the charm monster spell and just walk a distance away and let them follow you, and kill whatevers nearby. You can switch away to aim or suchlike while they kill stuff for you, and you can then switch back to graal and move again every few minutes. This works remarkably well except for when someone decides to be a punk and kill all your pets.. which gets extremely annoying, as it always seems to be some idiot on peaceful that does it. I led my army around the dungeon for about an hour last night (two lords, seven rexes, and even a few wolves/smokies

) while on aim talking to friends. I got around 6k exp in total (both magic and personality), maybe more.
I know this is a rather long post, but I hope it helps. If you have any questions, feel free to ask, I'd be glad to help.