Idiomatic Clojure? Performant & functional enough?
I am a journeyman myself in clojure, and I don't have answers for all of your questions, but I have some input.

I am not sure I fully understand your algorithm, but it seems you really have two loops rolled in to one. You have an inner loop looking for what could be the next tile to paint (without counting i), and an outer loop actually filling pixels and counting i down from n. Maybe it could be clearer if you separated these two somehow.

And since you choose candidates on random, it will be random how long it takes for you to fill n tiles.

I have found that when I do:

(loop [result ()
       input input-seq]
    (let [item (computation input)]
        (recur (conj result item) (rest input)))


It can often be re-written as:

(reduce computation input-seq)


(But I can't immediately see if this applies to your function)

Have you considered implementing this using a 2d array of tiles, instead of a list of coordinates?

A couple of other issues:


you can create a function which always returns true with: (constantly true)
I really like the use of (for (map +)) for vector addition, but you can use (mapv) instead of (vector (map))