My koi pond in my garden is not big, about 4x3ft and around 24" deep. You can keep Koi in a pond without it having to be thousands of gallons but you just have to know when to replace them. Koi grow at a decent rate but not as fast as some other fish like some of my Cichlids so you can have the same Koi for a few years till they start to outgrow the pond size. Good thing is it is easy to sell a good size Koi for decent money. So you can buy small Koi for $5-$10 at 3-6" range and have them in your small pond till they get to be 10-12" range then sell them to either the local pond supply store, or in my case I belong to a local Cichlid club and most the members have ponds so it's easy for me to sell them to other club members once they outgrow my pond. I'm probably going to go bigger on my pond next year though and redig it to about 500-600 gallon range.
As someone else said, build your own filter for your pond. I use 5 gallon bucket painted black to blend in, install a 710gph pump in the top under the lid with the hose coming out the top. Then I layer the bucket with media in the bottom, pads in the middle, and floss in the upper. All water draws in through holes drilled in the bottom of the bucket so it' works as a submersible canister style filter.
This is a pair of them like I just described, I made these two for my sisters 700g pond just last week....
Algae can be a problem in any pond, especially one that is new and not yet established. Usually you'll get a diatoms bloom of brown then green after that. Long as you have good filtration and a good quality algae treatment chemical then it will usually go away pretty fast. The best I have found is called Algae Fix and it's made by the company Pond Care. I wouldn't bother with plecos (algae eaters) in a pond. Most common plecos expend more waste (raising Nitrates) than the algae they consume so it's not really worth it. Bristol nose plecos eat a fair share of algae but they are best left to aquariums and not ponds.
Right now I bring my Koi inside during the winter and keep them in 55-75g tanks in my Cichlid fish room. You can leave them outside though, just get a cmall pond heater to keep in the pond to keep the surface from icing over so the gases can escape and the fish will go into hibernation and be fine.
You get a chance to set one up give it a go Source. They are a really enjoyable thing to have and add a nice relaxing feel to the garden