I will note that in the question, you noted that you want 'no values to appear more than once for any given n,' but this does not make very much sense as it is a function of n. Thus when you input n, you will get $f(n)$ back, and this will always be the same (unless we change the definition of the function from one trial to the next, which I did not gleam was necessary from your question).
So I assume that you meant instead that no number would be hit by different n, i.e. that the function is "injective."
We'll go at this from a few different perspectives. Firstly, it is easy to satisfy your demand. For example, the function $g(n) = (0 + n*1) \mod{65^6 - (65^5)}$ will yield a number $y$, and then you could always take $x=y + 65^5$ - this will always fall in your range of numbers, and for the first $65^6 - (65^5+1)$ numbers, it will never repeat. This, it turns out, it maximal, as every possible number in the range is hit exactly once. Note that $65^6 - 65^5$ is roughly one thousand times larger than your needed range, so you have a good amount of wiggle room.
There are lots of choices available, and making them prime makes it easier (you are right). But it's not absolutely necessary.
However, you said that you wanted a somewhat random-seeming function. From this, I think that you wanted to be able to plug in different n and get "random" numbers. Of course, it then becomes problematic - how do you choose n? Will you just go through them? If the true goal is seeming randomness, then I don't think that a function of this style will every generate a random sequence. The fact that it's a constant increment is what gives it away. But choosing larger primes would perhaps make it seem more random (as it would loop around more, potentially obscuring the constant increment... temporarily).
Does that make sense?