Vegetables For Variety

leafy lettuce, oranges, peas, wild rice, zuchinni, squash, sweet potatoe, cantalope, water melon, brocolli, etc.

Blood worms, daphnia, black worms, and earth worms too...

Heck there's a lot you can feed him, but these are "treats", once to twice a week kinda treats. Staple pellets are good for everyday and contain several vitamins and minerals and protiens your goldie requires.
 
Those are all good suggestions, and I'll add brine shrimp to the list of meats. Another good suggestion is to plant your tank: not only will the plants provide a treat for your fish, but they're also good for filtering the water, etc.
 
hmmm...I'm afraid I've forgotten the names of the plants I have in there. I'll look at some pics and try to figure it out for you. I have three varieties of plant in there, only one of which they've ever touched. I've heard people talk about goldfish being hard on their plants, too, but for me this isn't the case: mainly they just nibble here and there, plus the plant keeps growing so I've had no problems. I'll get back to you about the name of the plant, if I can figure it out.
 
I tried Anachris and they nibbled but didn't destroy.

Planting the tank is a great idea for the fish as treats but, more so, for balancing the levels. Since you have a heavy bioload, you will end up with a big nitrate problem. The live plants will take care of that. That is why I'm planting my tank. It is the best thing you can do for them and yourself, or else you will have to do a 50-75% water change every day. Not fun. Not cheap.
 
Okay the plant I have in there, which they nibble at but do not destroy, is a sword plant of some type, probably amazon. I see now that on many people's sites this plant is not recommended, but it has prospered in my tank, so who knows. I haven't been able to figure out what the other plants are (but the fish don't touch them, so they wouldn't help your veggie problem - there's a ferny-type plant in there, and a grassy-type one). Here's a site I found which looks pretty comprehensive: http://www.well.com/~debunix/fish/goldfishPlants.html
 
I heard that no fish likes the taste of Hornwort, but I heard that from a guy at a pet store, and you know what that info is like. I'll try it out for you and let you know if you don't want to waste your money.
 
AquariaCentral.com