Elliptic curve parameter generation
First of all, for elliptic curves based on a prime field $F_p$, we always work with a prime $p$ that is the same size as our target subgroup.

The reason is quite simple: we could work in a proper subgroup based on a larger curve, but what would that buy us?  It becomes more costly (as all our internal computations are modulo $p$, and if $p$ is larger, those operations are more expensive), and it doesn't make it any more secure; the best attack still involves $O(2^{n/2})$ operations.

A side effect of this decision is to make step 3 quite simple.

$N$ will always be in the "Hasse interval"; $p - 2 \sqrt{p} + 1 \le N \le p + 2 \sqrt{p} + 1$, or in other words $N \approx p$. Since $p$ is an n-bit number, that means that if $N$ were to have an n-bit factor, well, $N$ would have to be that n-bit factor (there is a possibility is that $p = 2^{n} - \epsilon$, where $\epsilon &lt; 2 \sqrt{p}$; in that case $N \ge 2^n$ is possible; I'll ignore that corner case)

So, step 3 is effectively "test $N$ for primality"; that can be implemented quite efficiently.

As for your other questions:


The number of curves you'd expect to go through: if the probability of a curve order being prime is approximately the probability of a random number in the Hasse interval being prime, then we'd have an expected $\log{p}$ iterations.  However, I'm not certain about true that assumption is; I expect it is close.
What size of $p$ do we want?  As above, we pick a cofactor of 1, with $p$ being an $n$-bit prime; again, we could use a larger prime, but there doesn't appear to be any benefit from doing so.