What is the idiomatic way to prepend to a vector in Clojure?

Vectors are not designed for prepending. You have only O(n) prepend:

user=> (into [:foo] [:bar :baz])
[:foo :bar :baz]

What you want is most likely a finger tree.