JeffP - I notice you are in 'cuse. There is a great pond "farm" near Canandaigua. Check out their web site:
www.willowpondaquafarms.com
If you can take a road trip next spring/summer it is well worth it! The place is phenomenal!!!!!!!!!!!!
I do have a pond by the way. Mine is somewhat crescent shaped with a waterfall at one end, fountain at the other end. I am not sure on the size, it's on the small side. It doesn't freeze in the winter though. I have a little floating heater that keeps it from icing over. I purchased the heater at Central Tractor for twenty bucks about five years ago and it's still working!
The biggest problems I have had have been overfeeding, keeping the neighbor's Chow out of it, and another neighbor's cat that stalks the birds and koi. I have had the pond for about six years.
As for safety, how about a small arched bridge acroiss the center of it with rails? The curious little ones can look from teh bridge with safety. You can also put a net over the water surface which will help keep leaves out (probably not strong enough for a child though).
Willow Pond has been the source of most everything I use. I have purchased Koi, liners, pump - almost everything from them. They have great products and are very knowledgeable. They have a catalog that they mail out also.
The pond was what got me started with fish. I have had the pond for almost ten years now and it has been very satisfying. I find it to be very relaxing!
I hope you get your pond!
DrD