Level 15 should be high enough. Mystic Arrows and Medusa stones are useful for long range contact and 3-4 elementals are a good distraction. There is a chest in a cave behind Nessie. Some people like to replay the battle (re-enter Nessie's area from Mt Gigas Underwater Caves) until they can get "good" stuf from the chest. If I haven't gotten good stuff by the 3rd or 4th battle I just take my victory and move along.