To see that a linear map of vector spaces is a $(1,1)$-tensor, realize that such an object eats a vector $X$ and covector $\omega$ (linear form to $\mathbb R$!) and gives you a number, i.e. $$\mathbf T(X,\omega)=\sum_{i,j} X^i\omega_j\mathbf T(\partial_i,dx^j)=\sum_{i,j} \omega_jT^j_iX^i,\;\text{where }T^j_i:=\mathbf T(\partial_i,dx^j)\in\mathbb R.$$
In the previous formula one can see that a $(1,1)$-tensor "is" a matrix $T^j_i$ which takes a vector $X$ and gives a vector $\sum_i T^j_iX^i$, which is precisely the matrix characterization of a linear map between vector spaces, precisely the linear map $\mathbf T(\_,\cdot):V\rightarrow V$ given by $X\mapsto\mathbf T(X,\cdot)$.
Thinking of tensors as multi-dimensional arrays is indeed a conceptual understanding of what they are as long as you imagine them acting linearly on vectors. You may be interested in this long answer I gave at this other question concerning the concept and construction of covector in manifolds (and thus generalizing to tensors). You can think that your multi-dimensional multi-linear arrays have their entries smoothly dependent on the points of the manifold, in such a way that the whole object remains linear when acting on smooth vector fields (i.e. sections of the tangent bundle). For this to be true, their components have to transform in a particular way (generalizing the transformation law derived at the linked answer above).
If covectors are smoothly varying linear forms $\omega\vert_p :T_pM\rightarrow\mathbb R$ such that $\omega (aX+bY)=a\omega(X)+b\omega(Y)\in\mathbb R$ for all $a,b\in\mathbb R$ and any smooth vector fields $X,Y\in TM$, then they are completely determined, by linearity (check!), by their action on any coordinate basis of any chart: $$\omega(\partial_i)=:\omega_i\Rightarrow \omega (X)=\sum_i X^i\omega(\partial_i)=\sum_i X^i\omega_i\,.$$
Since $X^i$ and $\omega_i$ are by definition of vectors and covectors smooth scalar fields on $M$, we have checked that indeed such $\omega$ are the linear forms $TM\rightarrow\mathbb R$. Now, define covariant $k$-tensors to be similarly generalized from punctual multi-linear forms $\Omega\vert_p:\otimes^k T_pM\rightarrow\mathbb R$, that is to say, linear functionals on $k$ vectors fields: $$\Omega(aX_1+bY_1,X_2,...,X_k) =a\Omega(X_1,...,X_k)+ b\Omega(X_1,...,X_k)\text{ and similarly for the other slots}.$$
Because of this multi-linearity, their definition as action on a number of vectors reduces to action on coordinate basis: $$\Omega(\partial_{i_1},...,\partial_{i_k}) =\Omega_{i_1...i_k}\Rightarrow \Omega(X_1,...,X_k)=\sum_{i_1,...,i_k}X^{i_1}_1\cdots X^{i_k}_k\Omega_{i_1...i_k}\,.$$
In order to extend this algebraic (co)-tensors at every point to tensor fields on the manifold, their multi-array components $\Omega_{i_1...i_k}(P)$ must be smooth functions on the points $P\in M$, i.e. $\Omega_{i_1...i_k}:M\rightarrow\mathbb R$, but for the whole array to behave coherently and multi-linearly, since vectors transform between charts by the basis transformation, their components must patch together as: $$\partial'_i=\sum_j\frac{\partial x^j}{\partial y_i}\partial_j\Rightarrow \Omega'_{i_1...i_k}:=\Omega(\partial'_{i_1},...,\partial'_{i_k})=\sum_{j_1,...,j_k}\frac{\partial x^{j_1}}{\partial y_{i_1}}\cdots\frac{\partial x^{j_k}}{\partial y_{i_k}}\Omega_{j_1...j_k}\,.$$
This is the reason to the, too often, confusing fact that the components of a covector transform as the basis of vectors, and the components of a vector as the basis of covectors!
If you generalize this to include contravariant $k$-tensors $A\vert_p:\otimes^k T_p^*M\rightarrow\mathbb R$, it is easy to deduce that their transformation between charts has the oposite jacobian matrices. Finally you put together all this to define $(r,s)$-tensors $T\vert_p:\otimes^r T_pM\otimes^s T_p^*M\rightarrow\mathbb R$, which are multi-linear objects which take $r$ vectors and $s$ covectors and give numbers, make them into tensor fields by letting their array components to vary smoothly on $M$ and ensuring their patching on overlaping charts to preserve linearity by:
$$T'\,^{i_1...i_s}_{j_1...j_r}=\sum_{l_1,...,l_s}\sum_{k_1,...,k_r}\frac{\partial x^{k_1}}{\partial y_{j_1}}\cdots\frac{\partial x^{k_r}}{\partial y_{i_k}}\cdot\frac{\partial y^{i_1}}{\partial x_{l_1}}\cdots\frac{\partial y^{i_r}}{\partial x_{l_k}}T^{l_1...l_s}_{k_1...k_r}\,.$$
Therefore, indeed you can think of tensors as general multi-linear multi-dimensional arrays of smooth real functions on every chart of your manifold, such that all of them patch together nicely on the charts' intersections (think of charts as coordinate systems, like observers in physics, so any of them has a bunch of functions making these arrays, and any two observers agree they are talking about the same array-object by checking that their action on any input is the same regardless of their coordinate transformations). So actually, you end up realizing that you could have defined tensors as sections of the tensor product bundle of several copies of the tangent and cotangent bundles, since that is the most geometric, intrinsic and coordinate-independent definition possible. By taking only anti-symmetric covariant tensors you get the differential forms of the other answer.
Background: I work in the field of numerical relativity. I've read Carroll's book, but not recently.
It's pretty common for physics students to reach this point in their education, not really knowing anything about what tensors are or how they're talked about in higher mathematics. That's not really the students' fault. If your education was anything like mine, your first exposure to this stuff probably came from an electromagnetism course, or maybe a classical mechanics course. You stuck with vector calculus, and maybe the odd matrix now and then to do transformations, and that's all you needed.
Let's start with matrices, though: you might've thought of matrices as arrays of numbers, just with some funny "matrix multiplication" operation that lets you multiply matrices and vectors to get other vectors. That's good enough to do the computation, but it's a very narrow way of looking at things.
Instead, think of the matrix abstractly as corresponding to a vector-valued linear function of a vector. It's a vector field! Right? A vector-valued function of a vector is, according to everything you've been taught, a vector field. The only additional property we're imposing is that this function be linear.
Example: consider the matrix
$$T = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}$$
You can write $T$ like a function. Given a vector $\vec v$ and a basis $\vec u_1, \vec u_2, \vec u_3$, you could write
$$\begin{align*} T(\vec v) &= [(a \vec u_1 + b \vec u_2 + c \vec u_3) \cdot \vec v ] \vec u_1 \\ & + [(d \vec u_1 + e \vec u_2 + f \vec u_3) \cdot \vec v ] \vec u_2 \\ & + [(g \vec u_1 + h \vec u_2 + i \vec u_3) \cdot \vec v ] \vec u_3\end{align*}$$
Each of those dot products is just doing the row-column approach to matrix multiplication that you already know. This expression, for a general matrix, is rather tedious and tiresome, but most geometric transformations can be written more compactly.
So, a matrix isn't just an array of numbers with some arcane multiplication rule attached. It corresponds to a linear function--a linear map, as mathematicians would say. You can see in the above example that the components of the matrix correspond with the basis we used to write out the function $T$. If you change basis, you change components. That much becomes obvious when written this way.
General tensors correspond to maps just as matrices do. Here, we showed a matrix can correspond to a map from a vector to a vector. A tensor could map a vector to another vector, or a vector to a covector, or several vectors to a scalar, for instance.
On component transformation laws: physicists usually have the point of view that a change of basis doesn't change the underlying vector being described; it merely changes the basis used to describe that vector. The change of basis means you have different vector components, but the vector itself hasn't changed. When you think of a tensor as a map---as some linear function--you ought to be able to describe the arguments in any basis you like. This changes the components of the tensor as described in that basis, but not the tensor itself.
Now, even this answer is only just the tip of the iceberg. I would definitely criticize physicists for not presenting tensors as linear functions; if they had put more emphasis on this, the transformation laws would be obvious from the chain rule and hardly need comment.
However, I think a physicist should not be so eager to treat geometric objects (like vectors and such) as general tensors. You can do this, but doing so deprives you of the geometric intuition you have probably built up. Instead, geometric objects like tangents directions to curves, tangent planes to surface, and the like, should be thought of as elements of an exterior (or clifford) algebra instead. These formalisms let you ignore the "map" definition of vectors and such, so you can focus on building planes, volumes, and the like.
For calculus at this level, it seems the mathematician's preferred tool of choice is differential forms. A physicist might find forms inelegantly integrated into Carroll's text alongside the vanilla, index-manipulation sludge of plain old tensor calculus. Do yourself a favor: at the least, learn forms. It makes all the calculus here as easy as electromagnetism's vector calculus was. I have issues with some of the conventions that forms people tend to use--for reasons totally irrelevant to general relativity, forms people prefer to do everything in terms of forms, and not in terms of actual $k$-vector fields, which is an arbitrary choice, but it leads to circuitous garbage like defining inner products in terms of the Hodge star, which is backwards as sin--but it's still a big improvement over index manipulation.
Best Answer
Yes, you can regard a vector $v \in V$ as a linear map from $V^*$ to the underlying field of $V$, and as such it is a $(1,0)$ tensor. Similarly, a dual vector $u\in V^*$ is a $(0,1)$ tensor.
I am not sure what you mean by “if your vector is a non-square matrix”. I cannot think of a natural (i.e. basis independent) way of representing a vector as a non-square matrix.