When you're ready to move out of the safe zone, kill hags, ice elementals (they're villains too), arctic bears, and giants.
If you're just starting, you can spend some time in the sewers of any major city to get started with a bunch of leather... enough to take you to hardened by the time you finish the less time-consuming feats. Bring a skinner or three and go as a warrior in few pieces of chain to make life easier. Depending on the RNG, you could walk out of there with anywhere from 1 to 30 selentine keys, too. If you don't get very lucky on the keys, then you could try to fish up some maps for some gold. You can also sell the leather to players if you don't plan to use it.
You can put 25 points in any skill extremely cheaply, so don't be afraid to spend a few points. Even 50 isn't too much on the larger scale of things.
Try to farm spawns with 3+ people. The spawn rate goes up a lot.
http://yourmom.at/agon/has a map of spawns. I think it takes a lot of the enjoyment out of exploration, but it's a very useful tool.
Avoid soloing. If you really must solo, then at least hunt some stuff near spawns your clanmates are farming so you can call for help if you get jumped. It takes about 2 minutes to cross a square of the map lengthwise.