Why does it only take about 600 m/s more than Earth's escape velocity to have an encounter with Mars while it takes much more Delta v (about 3 km/s) from a solar orbit (same as Earth orbit) to have an encounter with Mars?
What explains this difference?
Is it the Oberth effect or something else that explains this?
Yes, it seems related to the Oberth effect. Starting from the solar orbit, we need $\Delta v$ to enter an orbit to Mars. By energy conservation the velocity of the spaceship at launch from Earth has to be $$v_0 = \sqrt{v_{\text{esc}}^2+\Delta v^2} \ ,$$ where $v_{\text{esc}}$ is the escape velocity. For $v_{\text{esc}} \gg \Delta v$, we find that the $\Delta v^{\prime}$ on top of the escape velocity is $$\Delta v^{\prime} \simeq \frac{1}{2}\frac{\Delta v^2}{v_{\text{esc}}} \ .$$ This formula relates your Delta-v's in your question. We observe that $\Delta v^{\prime}$ becomes smaller the bigger the escape velocity from Earth. Bigger escape velocity means that you're deeper in the gravitational well. By the Oberth effect, a small Delta-v deep in the gravitational well has a bigger effect outside of the well.
In fact, irrespectively of the above approximation, we always have $$\Delta v^{\prime} = \sqrt{v_{\text{esc}}^2+\Delta v^2}-v_{\text{esc}} \leqslant \Delta v \ .$$
