The paper:
J. C. Lagarias, H. L. Montgomery and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979) 271-296
gives a bound of the form $c \sqrt p$ for some unspecified $c$.
My paper with J. Vaaler:
The least nonsplit prime in Galois extensions of Q, J. Number Theory, 85 (2000), 320-335.
gives an effective constant (when $K=\mathbb Q$, but the argument should generalize). Actually, the quadratic field case of our argument is already in Gauss. Our paper has a bunch of other references, including what you can get with GRH. Improving the square root bound without GRH is a big open problem.
The paper also gives me Erdos number 2 :-)
EDIT: As in GH's answer, the natural quantity for the bounds is the discriminant, so $p$ needs to be replaced by $p^n, n=[K:\mathbb Q]$, in the case of $K(\sqrt p)$. Here is an example where this will make a big difference. Take $K$ to be the cyclotomic field of $p$-th roots of unity where $p \equiv 3 \mod 4$, so the quadratic extension is non trivial. The OP asks for degree one primes, these are primes above rational primes $l \equiv 1 \mod p$, so they have norm $l > p$ and you can't expect a $\sqrt p$ bound.