There are two mathematical concepts which are both called vector. The first one, the vector from linear vector space is the basic "multicomponent object" which you seem to mainly talk about. The second notion of a vector is of a member of the so-called "tangent bundle" of a manifold. The second notion is the one which is defined equivalently with the physical vector.
The mathematical linear vector space
The mathematical linear vector space just refers to any object which can be added, multiplied,... but may be more than a mere number (i.e. have more components). Your mathematical vector might be for example "fruit collection" with the basis being one apple and one orange. You can have two apples and 3 and a half oranges represented by a vector $(2,3.5)$. You can double your fruit collection $2\cdot(2,3.5)=(4,7)$, or you can add your fruit collection to a friends fruit collection of $A$ apples and $O$ oranges $(2,3.5)+(A,O) = (2+A,3.5+O)$. You can even get into "fruit debt" by borrowing and eating fruits and have negative fruit collections. This is a perfect mathematical linear vector space.
You can find out that for example certain kinds of functions span an infinite-dimensional linear vector space with the values of the function acting as components $V_i \to V_x = V(x)$. Once again you can even define a "dot product" by summing over the infinite components $\vec{V}\cdot \vec{W} = \sum_i V_i W_i \to \int V(x) W(x)$. And so on. This was just to show that the mathematical linear vector space is a label for very general objects far beyond the extent of a physical vector in 3D space.
The physical vector
We talk about a vector in Euclidean space without distinguishing where it "lives". When we draw a picture of the arrow of say the velocity vector in 3D space, do we mean the tip of the arrow actually does touch the point in space where it ends? Surely not, this would be only true for the distance vector.
We must now draw a line between objects we call vectors in physics. One kind is the distance vectors, which do not transform as a vector unless they point from the origin, and "polar" vectors, the real physical vectors. These polar vectors include: velocity, force, acceleration and electric intensity. (Vector products of "axial" and polar vectors are also polar vectors.)
We know how points in space transform under coordinate transformations and the velocity vector is actually a tangent to two infinitely close points in space. From this fact, we can deduce how velocity transforms - the points transform according to the coordinate transformation, and the velocity vector transforms according to the difference of the transformation in infinitely close points - the Jacobian matrix. This can be shown to be true also for the acceleration vector.
Now we want to formulate equations for velocities and accelerations - it is necessary that these equations give us the same results no matter how we choose to describe the situation. Thus, we require that all the other terms in the equation transform the same way as velocity/acceleration under coordinate transforms. You probably already know this as the principle of covariance. This is the only motivation of the definition of "the true physical vector".
However, when considering a new physical quantity, we cannot just define it to be covariant with velocity - we must explicitly show that an object is consistently transforming this way due to physical arguments. This is the reason why the physicists usually give a down-to-earth technical definition of a vector by transformation, because in many cases this is the most practical formulation for actual computation.
The physical tensor
Physical tensors arise mainly in the context of continuum mechanics. Say we don't want to trace the evolution of one point, but an infinitely small deformation of an infinitely small cube. For this, we need three vectors showing the deformation of every edge of the cube (9 components in total) making it a "vector of vectors".
It is intuitive that every of these 3 deformation vectors showing an infinitely small deformation will transform with the Jacobian matrix. These vectors are however not independent - say the cube rotates by an angle - then the 3 deformation vectors mix and for an infinitely small cube this is again executed by the Jacobian matrix. That is, we multiply every vector of the "vector of vectors" by the Jacobian and then also mix them together by multiplying the whole "vector of vectors" by the Jacobian.
In general, the concept of vectors and tensors is linked to the linearization or differential localization of a given physical fact always leading to transformations via the Jacobian matrix. It is a non-trivial statement of classical physics which tells us that through the description of these linearizations, we can describe the behaviour of the whole.
Tangent spaces and vectors living in them
The mentioned physical ideas can be straightforwardly reconciled with some mathematical ones. The most intuitive way to see why vectors aren't living in the same space as the physical points, is to picture a curved surface with a trajectory on it. The velocity vector of the trajectory points generally "outside" the surface. Nevertheless, all the possible velocity vectors at a given point span only a two-dimensional surface which is tangent to the curved surface at that point.
Mathematicians take this notion and define a tangent manifold at every point of a space as the space of tangent vectors to trajectories at a given point (they do it with a clever trick which makes the term "tangent to a trajectory" well defined). The tangents to trajectories can than be shown to transform once again with the Jacobian matrix and span a mathematical linear vector space in every point. When we take the whole ensemble of "tangent surfaces" or tangent manifolds, we get something we call a tangent bundle.
So, physical vectors actually live in these tangent manifolds attached to every point in space, not in the space itself. Tensors can be also very easily generalised as "vectors of vectors" living in "tangent manifolds times tangent manifolds".
The coincidental structure of the flat space and the flat tangent manifold leads to more or less harmless confusion, but this has to be resolved once we are moving around in a curved space(-time).