Indexing a random permutation I am curious if there exists a method for specifying a permutation $F_k: X \to X$ with a small(ish) $k$.

Something that comes very close to my goal is a block cipher, say AES. But block ciphers have fixed block size (e.g. 64, 128 bits), and I want something with parameterizable (and smaller) "block size" $\log_2 |X|$. I also don't need many characteristics of block ciphers (e.g. $k$ secrecy, etc.), only the permutation part.

Something else that is quite close is the Lehmer code. However, this takes into consideration all possible permutations $|X|!$, and would need the index (or "key") $k$ to be as large as $|X| \log_2 |X|$. I am happy with only $K &lt;&lt; |X|!$ possible permutations (so long as $K$ is "big enough").
You can build a block cipher with any desired block size, using a method called "format preserving encryption".  The block size doesn't have to be limited to 64 bits or 128 bits.  This will provide a reasonable solution to your problem.

See Bijective algorithm(s) that can shuffle a range of numbers back and forth, Pseudo random, unqiue integer numbers in a given range, Invertible function that randomizes order, Efficiently generating a uniformly random list of unique integers in a range, Lazily computing a random permutation of the positive integers.