Would you consider dropping the dependency against ido-vertical-mode?
I use a modified version of your package with ido-grid-mode without explicit dependencies.
No require or what so ever, things just work. I think that most users of ido-vertical-mode will have it enabled at all time, thus no need for you to depend on it or alternate ido packages.
A recommendation could be, please use ido-grid-mode or ido-vertical-mode with this package.