Since you can't really mix tropicals with coldwater fish...you might try some other coldwaters like white cloud minnows? I'm not sure if the koi would eat them...since the minnows really dont get too big.
Ghost shrimp would probably get eaten too...but their natual habitat is ponds so I think they'd be fine in cooler water.