Lower bounding the probability that $\gcd(t,N)≤B$, for a random $t$ and fixed (large) $N$ $\newcommand{\Prb}[1]{\mathcal{P}_{#1}}$
I have the following number theory problem, related to Odlyzko's improvement on Shor’s factoring algorithm (see this cstheory.sx question for details).

Let $N$ be a (large) integer and $1≤B≤N$ a bound. If I chose the integer $1≤t≤N$ uniformly at random, can I lower bound the probability $\Prb B$ that $\gcd(t,N)≤B$ ? How should I chose the least possible $B$ such that $\Prb B$ is bounded away from 0 ? Or asymptotically close to 1 ?

Of course 
$$\begin{align}\Prb 1&=\frac{ϕ(N)}N>\frac{1}{e^γ\ln\ln N+\frac3{\ln\ln N}};& \Prb N&=1 \end{align}$$ 
where $ϕ$ is Euler’s totient function and $γ$ is the Euler-Mascheroni constant.
More generally, it is easy to see that 
$$
\Prb B=\frac{\sum_{d\vert N}^{d≤B}ϕ(\frac{N}{d})}N
 =1-\frac{\sum_{d'\vert N}^{d'<\frac{N}{B}}ϕ(d')}N,
$$
but I did not manage to go further.
If I interpret the 1995 “private communication” from Odlyzko to Shor (referred to in arXiv:quant-ph/9508027 and the cstheory.sx question) correctly, $∀ε>0$, $\Prb{(\log N)^{1+ε}}$ is bounded away from 0. However, I did not manage to find a proof of this.
 A: A justification of Odlyzko's comment has already been provided. Let me supplement this by saying that if you want the probability to tend to 1, you should take $B = (\log{N})^{A}$, where $A \to\infty$ with $N$.
That this is sufficient follows from Terry's answer above. To see it is necessary, let me show that if A is any fixed constant, then $\mathcal{P}_{(\log{N})^A}$ does not tend to $0$ as $N\to\infty$. Let $N$ be the product of the primes up to $z$, where $z$ is a parameter tending to $\infty$. (So $\log{N} \sim z$, by the prime number theorem.) Consider numbers $t \le N$ constructed as a product $de$, where $d$ is squarefree, $z$-smooth, $d \in ((\log{N})^{A},(\log{N})^{2A}]$, and $e$ has no prime factors up to $z$. Then $\gcd(t,N) = d > (\log{N})^{A}$; we will show below there are $\gg N$ such values of $t \in [1,N]$.
Given $d$, the number of possibilities for $e$ is $\gg \frac{N}{d \log{z}} \gg \frac{N}{d \log\log{N}}$, by (e.g.) Brun's sieve. Now we sum on $d$. For $T \le (\log{N})^{2A}$, the number of squarefree $z$-smooth integers $d \in [1,T]$ is $\gg T$. (The distribution of squarefree smooth numbers is understood in quite a wide range; e.g., see work of Naimi.) Now partial summation gives that the sum of $1/d$ is $\gg \log\log{N}$.
A: In fact one can prove a stronger result -- namely the probability is bounded away from zero, so long as $B \ge (\log N)^\delta$ for some $\delta >0$.  This is best possible, by taking $N$ to be the product of the first few primes.  Since $\phi(N/d) \ge \phi(N)/d$, our probability is bounded below by 
$$ 
\frac{\phi(N)}{N} \sum_{d|N, d\le B} \frac{1}{d}\ge \frac{\phi(N)}{N}\sum_{d|N, d\le B} \frac{\mu(d)^2}{d}, 
$$ 
where in the last sum we have restricted attention to square-free $d$ for simplicity. 
Now I claim that for large enough $B$ (and any $N$, independent of $B$) one has 
$$ 
\sum_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \frac{1}{4} \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big). \tag{1} 
$$ 
Assuming the claim, we get a lower bound for our probability of 
$$ 
\ge \frac 14 \frac{\phi(N)}{N} \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) 
\ge \frac{1}{4} \prod_{p} \Big(1-\frac 1{p^2}\Big) \prod_{p|N, p>\sqrt{B}} \Big(1-\frac 1p\Big)= \frac{3}{2\pi^2} \prod_{p|N, p>\sqrt{B}} \Big(1-\frac{1}{p}\Big).  
$$
If now $B\ge (\log N)^{\delta}$ then 
$$ 
\prod_{p|N, p>\sqrt{B}} \Big(1-\frac 1p\Big) \ge \prod_{(\log N)^{\delta/2}<p <(\log N)^2}\Big(1-\frac 1p\Big) \prod_{p>(\log N)^2, p|N} \Big(1-\frac 1p\Big),
$$ 
and by Mertens's theorem the first factor above is $\gg \delta$, and trivially the second factor is $1+o(1)$.  This completes the proof. 
It remains to settle the claim (1).  With $\alpha =1/\log B$ note that 
$$ 
\sum_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \sum_{\substack{d|N, d\le B \\ p|d \implies p\le \sqrt{B}}} \frac{\mu(d)^2}{d} \ge \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) - B^{-\alpha} \sum_{\substack{d|N\\ p|d\implies p\le \sqrt{B} }} \frac{\mu(d)^2 d^{\alpha}}{d}.
$$
The second term above is 
$$ 
e^{-1} \prod_{p|N, p\le \sqrt{B}} \Big(1 + \frac{p^{\alpha}}{p}\Big) \le e^{-1} \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) \exp\Big(\sum_{p|N, p\le \sqrt{B}} \frac{p^{\alpha}-1}{p}\Big).
$$
Now for large enough $B$, (since $(e^{t}-1)/t \le (\sqrt{e}-1)/(1/2)$ for $0\le t\le 1/2$)
$$ 
\sum_{p\le \sqrt{B}} \frac{p^{1/\log B}-1}{p} \le\sum_{p\le \sqrt{B}} \frac{\log p}{p\log B} \Big(\frac{\sqrt{e}-1}{1/2}\Big) = \sqrt{e}-1 +o(1),
$$
and using this above, we obtain 
$$ 
\sum_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) \Big(1- e^{-1} (e^{\sqrt{e}-1}+o(1)) \Big) \ge \frac 14 \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big), 
$$
proving the claim (1).
A: One can establish the claim using a logarithmic version of the moment method.
If one factors $N = \prod_{p|N} p^{\operatorname{ord}_p(N)}$, then $\log \operatorname{gcd}(t,N) = \sum_{p|N} \log \operatorname{gcd}( t, p^{\operatorname{ord}_p(N)} )$.  Taking expectations, we see from linearity of expectation that
$$ {\mathbf E} \log \operatorname{gcd}(t,N) \leq \sum_{p|N} \sum_{1 \leq j \leq \operatorname{ord}_p(N)} \frac{j \log p}{p^j}$$
since the event $\operatorname{gcd}(t,p^{\operatorname{ord}_p(N)}) = p^j$ occurs with probability at most $1/p^j$.  The contributions of $j \geq 2$ can be bounded by $O( \sum_p \frac{\log p}{p^2} ) = O(1)$ after summing first in $j$, hence
$$ {\mathbf E} \log \operatorname{gcd}(t,N) \leq \sum_{p|N} \frac{\log p}{p} + O(1).$$
By Mertens' theorem, the contribution of those primes up to $\log N$ is at most $\log\log N + O(1)$.  As for the primes greater than $\log N$ that divide $N$, there are at most $\frac{\log N}{\log\log N}$ of these, and each term is at most $\frac{\log N}{\log\log N}$, so the total contribution is $O(1)$.  Thus
$$ {\mathbf E} \log \operatorname{gcd}(t,N) \leq \log\log N + O(1).$$
By Markov's inequality, this implies that $\log \operatorname{gcd}(t,N) \leq (1+\varepsilon)\log\log N$ with probability bounded away from zero for $N$ sufficiently large depending on $\varepsilon$, which gives the claim.  
