With soils like that, and knowing a little about your climate, you will definitely want a rubber-lined pond. You can get standard off-the-roll sizes 40' wide, so a 40x40 sheet will easily hit a 25x25 pond, if not more. At least I think you still can get 40' wide rolls.

That size hole you can dig by hand, or rent an excavator to do it.

Starting right off with rubber will prevent any worry about leaking or importing clay to the site. Yes, the stuff is expensive, but so it trying to fix leaks, and with your soil, why take chances?

Oh, 25x25 shrinks really quick once you get into the hobby. My 10x15 looks like a driveway puddle to me now, and planning on increasing it to 20x15 this summer along with a small deck. One good pond lily can easily take up a 10x10 area.