The radius of a non-rotating black hole is $$r_s = \frac{2GM}{c^2} \tag{1}$$
where $M$ is the mass, $G$ is Newton's constant, and $c$ is the speed of light. This is the distance from the center of the black hole to the event horizon. The event horizon is the surface that traps light and objects, it separates inside and outside the black hole. Anything that passes inside the event horizon can never escape, even light. This is why it is said that the escape velocity at the surface of a black hole is $c$.
It is also the case that any object with $r < r_s$ is a black hole. But since the mass should be roughly proportional to the volume, and the volume is proportional to $r^3$, anything heavy enough will form a black hole. Therefore from (1) the proper answer to your question is: because they are very massive, not because they are small.
The local escape velocity is
$$v_{esc} = \sqrt{\text{2 G M}/\text{r}}$$
At infinty you observe that velocity slower by a factor of
$$1-\text{r}_s/\text{r}$$
so at infinity you observe
$$\text{v}_{esc} = \sqrt{\text{2 G M}/\text{r}} \cdot (1-\text{r}_s/\text{r})$$
because of gravitational length contraction radial to the mass and gravitational time dilation in all directions.
The local orbital velocity is
$$v_{orb} = \sqrt{\text{G M}/\text{r}}/\sqrt{1-\text{r}_s/\text{r}}$$
which is at infinity observed to be slower by a factor of
$$\sqrt{1-\text{r}_s/\text{r}}$$
At infinity you observe simply
$$\text{v}_{orb} = \sqrt{\text{G M}/\text{r}}$$
So the observer at infity should observe an orbiting particle orbit with it's newtonian velocity, while locally this velocity is higher.
The Plots show the velocities in terms of v/c and the Schwarzschild r coordinate in units of GM/c². Left is the system of a local observer, and right like an observer at infinity would see the Shapiro-delayed velocities.
Locally the escape velocity equals the orbital velocity at r=4GM/c², while at infinity their equality is observed at r=2·(2+√2)=6.8284GM/c².
At the photon sphere a local observer would observe the orbiting particle with c, while an observer at infinity would measure it slower by a factor of √(1-2/3), so with 0.577c.
An escaping particle near the event horizon would need a local radial velocity of c, and seem to have zero velocity for the observer at infinity.
The different factors for the radial and the transversal components is due the graviational length contraction which is only in radial direction (there is more radius inside the circle than the circumference divided by 2π).
To sum it up:
Locally, the radial escape velocity for Einstein is the same as for Newton. At infinity it is observed slower than that.
Also locally, the angular orbital velocity for Einstein is higher than for Newton, but at infinity it is observed to be the same as it would be under Newton.
The escape velocity can be lower than the orbital velocity, therefore orbits near the photon sphere are unstable in a sense that if your velocity is not only transversal but splits into a transversal and a radial component you will escape to infinity. With Newton you would just get an elliptical orbit with everything else staying the same.
Radial:
Transversal:
Comparison with Newton:
The index is in german, but I'm sure you'll find the local $v$ and the external $\text{v}$ (the latter with Shapiro delay).
Further reading: Equation of Motion and Geodesics, page 4, eq(9)
Code
Best Answer
Unlike with the other answer, my presumption is that you're asking about the largest possible escape velocity from a stable object that's not a black hole. I.e., the circumstances you're considering don't include a situation in which the "object" involved includes some matter that's in the process of being rapidly expelled. The best candidate for such an object that's moderately well understood is likely a neutron star.
The relationship between density and mass of a neutron star isn't very precisely understood; there are a number of somewhat differing models for a neutron star's equations of state. There may well even exist quark matter that's even denser than the neutron degenerate matter that's thought to form the bulk of a neutron star, but that's venturing off even further into the limits of what's currently known.
However, according to some equations of state, there can exist "ultracompact" neutron stars which are so dense that they have a photon sphere. A photon sphere occurs at the radius at which a photon can orbit the object in question in a circle. In Schwarzschild coordinates, the photon sphere occurs at 1.5 times the Schwarzschild radius. I.e., the photon sphere occurs at a radius given by
$$r_{ps}=\frac{3GM}{c^2}\ \ .$$
Using $r_{ps}$ as the radius in the equation for escape velocity,
$$v_e=\sqrt{\frac{2GM}{r}}\ \ ,$$
which is valid even relativistically, gives that the escape velocity from a photon sphere is
$$v_e=\sqrt{\frac{2}{3}}c \approx 0.816c\ \ .$$
So it appears that there can exist stable objects (ultracompact neutron stars) which are not black holes, but which require an escape velocity of more than 0.8c to escape from the surface.