For the first question, I think the answer is no. Consider the following example:
$X = Spec k[x,y,z]/(xy - z^2)$ a quadric cone. Consider the Cartier divisor $D = V(z)$. It has two irreducible components corresponding to the ideals $(x,z)$ and $(y,z)$ respectively (these are non-Cartier, Q-Cartier divisors). Both components smooth and they meet at the origin and so the multiplicity of $D$ (of this nodal singularity) is $2$. By multiplicity, I assume you mean the multiplicity of the scheme $D$ at a point.
On the other hand, if you blow up the origin $(x,y,z)$ you get a chart $$k[x/z, y/z, z]/( (x/z)(y/z) - 1).$$ The pull back of $D$ on this chart is just $z = 0$ (one copy of the exceptional divisor) so the order of $\mu^*(D)$ along $E$ is equal to 1. (The order of the components along the exceptional divisor is $1/2$ in each case, but they are $\mathbb{Q}$-Cartier)
There's a deeper problem in your first question though. If I recall correctly, in general, when you blow-up a point $x \in X$ on a singular variety, there isn't a unique prime exceptional divisor lying over $x$. There are probably multiple such divisors. To make matters worse, the pull back of your given Cartier divisor can have different multiplicities along these different exceptional divisors.
For the second question:
You assume that the pair $(X, \Delta)$ is klt, and you define the discrepancy at $E$ to be the order along $E$ of $K_Y - \mu^*(K_X + \Delta)$. Then you say that you know that $a(E, X, \Delta) \leq 1$ if $X$ is smooth. This isn't true.
I assume you know that the definition of klt implies that these discrepancies are all $> -1$. However, consider the following example.
$X = Spec k[x,y,z]$ and $\Delta = 0$. This pair is certainly klt. When you blow up the origin though, the relative canonical divisor $K_{Y/X} = 2E$, two copies of the exceptional (if you blow up the origin in $\mathbb{A}^n$, you get $n-1$ copies of the exceptional divisor). If you blow up points on that exceptional divisor (and repeat), you get further exceptional divisors with greater and greater discrepancy.
Hopefully I didn't misunderstand the question.
You want a divisorial contraction $Y \to X$ on a smooth 3-fold $Y$. Extremal divisorial contractions (i.e., contractions associated to a $K_Y$-negative extremal ray in the Mori cone of $Y$) have been classified by S. Mori in his paper
3-folds whose canonical bundles are not numerically effective, Annals of Mathematics 116, No. 1 (1982), pp. 133-176.
Looking at Theorem 3.3, we see that here are exactly the following possibilities:
the smooth blow-up of a point; in this case $S$ is isomorphic to $\mathbb{P}^2$ with normal bundle $\mathcal{O}(-1)$;
the smooth blow-up of a curve, in this case $S$ is a ruled surface whose normal bundle restricted to the ruling has degree $(-1)$; this is the situation described by Donu Arapura in his answer;
the contraction of a plane $S$ with normal bundle $\mathcal{O}(-2)$; in this case the
surface $X$ has an isolated singularity isomorphic to the quotient of $\mathbb{A}^3$ by the involution $(x,y,z) \to (-x, -y, -z)$;
the contraction of a smooth quadric $S$ whose rulings are numerically equivalent; in this case the image of $S$ is a single point, which is a singular point for $X$;
the contraction of a singular quadric $S$; again, the image of $S$ is a point in $X$.
Summing up, if you want that $X$ is smooth and the image of $S$ is a curve, the only possibility is 2.
In the case where $Y$ is a smooth 4-fold and $S$ is a smooth surface, the answer can be found in the paper of Kawamata "Small contractions of four-dimensional algebraic manifolds": in this case the only possibility is that $S$ is the disjoint union of copies of $\mathbb{P}^2$, with normal bundle $\mathcal{O}(-1) \oplus \mathcal{O}(-1)$
Best Answer
For a smooth $Y$, a necessary condition for contractibility is that the conormal line bundle $N_{Y,X}^\*$ is ample. It is also sufficient for contracting to an algebraic space. The reference is Algebraization of formal moduli. II. Existence of modifications. by M. Artin.
$Y$ can be contracted to a point on an algebraic (projective) variety if in addition $Y=\mathbb P^{n-1}$, $n=\dim X$. You can prove this easily by hands. Start with an ample divisor $H$ and then prove that an appropriate linear combination $|aH+bY|$ is base point free and is zero exactly on $Y$. You will find the argument in Matsuki's book on Mori's program for example.
So if $X$ is a surface and $Y=\mathbb P^1$ with $Y^2<0$ then it is contractible to a projective surface. For a reducible divisor $Y=\sum Y_i$ a necessary condition (which is also sufficient in the category of algebraic spaces) is that the matrix $(Y_i.Y_j)$ is negative definite. The strongest elementary sufficient condition for contractibility to a variety is that $\sum Y_i$ is a rational configuration of curves. This is contained in On isolated rational singularities of surfaces by M. Artin.
This paper also contains an example of an elliptic curve $Y$ with $Y^2=-1$ which is not contractible to an algebraic surface. The surface $X$ is the blowup of $\mathbb P^2$ at 10 sufficiently general points lying on a smooth cubic, $Y$ is the strict preimage of that cubic.
Finally, for an irreducible divisor $Y$ the resulting space $V$ is smooth iff $Y=\mathbb P^{n-1}$ and $N_{Y,X}=\mathcal O(-1)$. Indeed, $X\to V$ has to factor through the blowup of $V$ at a point by the universal property of the blowup. But then $X$ has to coincide with this blowup by Zariski main theorem. And on the blowup at a point the exceptional divisor is $\mathbb P^{n-1}$ with the normal bundle $\mathcal O(-1)$.