Randomly Choosing a N-Bit Prime
Actually you should be thinking about a geometric random variable, not a binomial RV, since you're interested in the number of times that you have to sample before you hit a prime. And each sampling event is actually a Bernoulli trial (with probability of choosing a prime $p = \Theta(1/\log {2^n}$), where $n$ is the number of bits).

And for showing that the expected value is $O(n)$, you don't need to show that it's less than $n$. You actually need to show that there are some constants $k$ and $N$ such that the expected value is less than $kn$ for all $n \ge N$.

But besides that, you're on the right track.