Are there explicit examples of smooth surfaces of degree 4 and 5 in P^3, which contain no lines or conics (i.e. smooth rational curves of degrees 1 and 2)? An example over a finite field would be better, but if not  I will take one over complex numbers :)

1$\begingroup$ What if you try something more basic than what is suggested below. E.g. for lines on degree 4 hypersurface in P^3. The choice of hypersurface is 35 coefficients (c_i). Then on a standard A^4 patch of Gr(2,4), you have 4 variables. The equations for one line to lie on the hypersurface will be a system of 5 equations in the (c_i). Do the same thing on the other patches of Gr(2,4). What happens if you turn on your computer and try to "randomly" find (c_i) so that none of these equations have solutions? Conics will of course be harder still, but maybe manageabl.e $\endgroup$ – unknown May 17 '10 at 20:55
The generic hypersurface of degree 5 in P^3 has no rational curves at all, let alone a line or a conic: see
G. Xu, "Subvarieties of general hypersurfaces in projective space", J. Diff Geom 1994
So you can certainly get a complex such hypersurface without any lines or conics just by embedding the function field of the moduli space of hypersurfaces into C. Since the locus of quintics containing a line or conic is a proper closed subvariety, you'll also get plenty of examples over finite fields if you make the finite field large enough (though to be fair this will not exactly be "explicit.")
I guess the generic quartic hypersurface probably also has no lines or conics (though it will have rational curves) but I didn't check this.
Explicit examples are hard to construct, even though as Jordan pointed out, most surfaces work. If you can compute the zeta function and check that the Neron Severi group has rank one, then there are no lines or conics. Kedlaya and some students have an algorithm to compute the zeta function. See their paper in the proceedings of AGCT 10.
http://smf4.emath.fr/Publications/SeminairesCongres/2009/21/html/index.php
I think that the quartic with equation \[ x^4 + y^4 + xy^2z + yw^3 + z^3w \] over $\mathbb{F}_2$ has no line and that it has no conic defined over a field of size at most $2^8$. Both statements I have checked using a computer, so there could be mistakes in the program I used, but I did some testing for the algorithm to decide existence of lines. For the algorithm for conics, I could never get it to finish, this is why I resorted to brute force search for some conic defined over a small field. If the example above works, then any quartic with coefficients in $\mathbb{Z}$ reducing to the one above modulo two, also has no line and no conic on it. Also, if it works, it is the only one with at most five monomials, up to isomorphism.
I will work over $\mathbb C$. Although I have not checked, the example below should work for characteristic different from $3$.
To exhibit a degree $d$ projective surface $S \subset \mathbb P^3$ not containing any line you can consider surfaces of the form $t^d = f(x,y,z)$ where $f$ is homogeneous polynomial of degree $d$.
Let $C \subset \mathbb P^2$ be the curve determined by the polynomial $f$ and $\pi: S \to \mathbb P^2$ be the linear projection from the point $p=[0:0:0:1]. $ If $\ell$ is a line contained in $S$ then $\pi(\ell)$ is a line tangent to $C$ at a total inflection point $q$, i.e. the contact between $C$ and the line $\pi(\ell)$ at $q$ is of order $d$. For details see Section 6 of Counting lines on surfaces by Boissière and Sarti.
This reduces the problem of finding a surface without lines to the one of finding an algebraic curve without total inflection points. For quartic curves we have not to look much, as Klein determined all the inflections of his famous quartic $$ x^3y + y^3 z+ z^3 x = 0. $$ All its $24$ inflection points are simple, see for instance Jeremy Gray's paper in The Eightfold Way: The Beauty of Klein's Quartic Curve. Thus the surface $$ t^4  x^3 y  y^3 z  z^3 x =0 $$ has no invariant lines.
It should be possible to pursue this argument further to determine the sought examples.
Edit: The quartic surface above ( as any quartic of the form $\{ t^4 f(x,y,z)=0 \}$ ) has many conics, as the preimage of a bitangent line (there are $28$) is the union of two conics. On the other hand, the surface $$ t^5  x^4y  y^4 z  z^4 x =0 $$ seems to be a good candidate for a quintic without lines nor conics.
A quartic surface containing a line or a conic has Picard number at least 2. There are explicit examples of Ronald van Luijk of quartic surfaces defined over $\mathbb{Q}$ such that the (geometric) Picard number is 1. (See http://www.math.leidenuniv.nl/~rvl/ps/picone.pdf) The reductions of these surfaces mod 2 and 3 contain a line resp, a conic, so they do not work for you. However, this paper hints at algorithm how to find examples in positive characteristic:
Take a smooth quartic surface $S$ over a finite field with $q$ elements. By point counting (or more efficient methods) you can determine the characteristic polynomial $P_2(T)$ of Frobenius on the second (etale) cohomology of $S$. Let $r$ be the number reciprocal zeros of $P_2$ the form $q\zeta$ with $\zeta$ a root of unity. This number $r$ has the same parity as the degree of $P_2$, which is $22$ for quartic surfaces. It is wellknown that $r$ is at most the geometric Picard number of $S$.
Suppose now that you find a surface such that $r=2$. Then either the geometric Picard number $\rho(S)$ equals 1, and you are done, or the geometric Picard number equals 2. In the latter case the Tateconjecture holds. Milne proved that the Tateconjecture implies the ArtinTate conjecture. Now the ArtinTate conjecture enables you to determine the discriminant $D$ of the intersection pairing on the NeronSeveri group up to squares from $P_2(T)$. (See, e.g. my paper on elliptic K3 surfaces with geometric MordellWeil rank 15.) Now if $\rho(S)=2$ and $S$ contains a line then $D=k^2$ for some integer $k$, and if $S$ contains a conic then $D=3k^2$ for some integer $k$ (this is an easy exercise). Hence you have a criterion to check whether your quartic surface contains a line or a conic. For quintics something similar works, only the degree of $P_2$ differs, and the values of $D$ in the case that $S$ contains a line or a quintic differ.