Is there any relationship between Free Pre-Lie Algebras and Free Algebras over the Operad Pre-Lie (like in KOSZUL DUALITY FOR OPERADS in pg 13 )? If there is, can someone indicate a reference for this?
So, why is a Free Pre-Lie Algebra the Free Algebra associated with Operad Pre-Lie? Moreover, is this true in general?
This is a general fact about operads. Let $\mathtt{P}$ be any operad (e.g. the pre-Lie operad) in a symmetric monoidal category $\mathsf{C}$. If I understand your question correctly, you have two definitions of "free algebra" you want to compare:
The forgetful functor $U : \mathtt{P}\text{-alg} \to \mathsf{C}$ has a left adjoint $F_\mathtt{P}$, and a "free algebra" is an algebra of the type $F_\mathtt{P}(X)$. It is characterized by the relation: $$\hom_{\mathtt{P}\text{-alg}}(F_\mathtt{P}(X), A) \cong \hom_\mathsf{C}(X,U(A)),$$ in other words any morphism $f : X \to A$ in $\mathsf{C}$ induces a unique morphism $F_\mathtt{P}(X) \to A$ that "extends" (along the morphism $X \to F_\mathtt{P}(X)$) $f$.
The "free $\mathtt{P}$-algebra" functor $S(\mathtt{P})$ which is given by: $$S(\mathtt{P},X) = \mathtt{P} \circ X = \bigoplus_{n \ge 0} \mathtt{P}(n) \otimes_{\Sigma_n} X^{\otimes n},$$ with a $\mathtt{P}$-algebra structure induced by the operad structure of $\mathtt{P}$.
Then both functors are naturally isomorphic. This is Proposition 5.2.1 in Algebraic Operads by Loday and Vallette. It's not too hard to prove, you should try it before reading the proof.