I think groups representations are the most natural way to understand tensors. The following parts can be read essentially independently. The 2nd is the most relevant.

Why tensors in physics can be confusing
=================
I think the primary source of confusion is that $X$-tensors always, always, always include structure that physics literature isn't too worried about making explicit. It's the **transformation law** that I mean by structure, under the transformations as implied by $X$ (this could be $X\in\{\text{"Lorentz" or 4},\text{"Euclidean" or 3},\dots\}$). 

The infamous question "Is my matrix here a rank 2 $X$-tensor?" can only be answered by "well, it depends". Because how are we to test whether your matrix is *transforming like a tensor* if you don't tell us *how your matrix transforms*.

Some element $A$ of a vector space (note that any $X$-tensor lives in a vector space: adding $X$-tensors makes an $X$-tensor and multiplying by $\lambda\in\mathbb{R}$ as well) can be confirmed to be a tensor *only if* you specify the following data: $$Data:=\{A \text{ how it looks in frame }1,A \text{ how it looks in frame } 2,\dots,A \text{ how it looks in last frame}\}.$$ 
Then we can compare with an $X$-tensor and can decide if this is exactly how our tensor transforms or not. If yes, A is by def. an $X$-tensor, otherwise not.

Tensor as an element of the representation of a group
======================
Fix a group $X$ (this could be $X\in\{\text{lorentz trafos},\text{rotations},\dots\}$ in direct correspodence to the first paragraph). Recall that an $n$-dim. representation of $X$ is by def. a group homomorphism ($\text{GL}$ are all invertible matrices)
$$\rho:X\rightarrow\text{GL}(\mathbb{R},n),\quad g\mapsto\underbrace{(T\mapsto g.T)}_{\text{matrix is a function}}\quad (T\in\mathbb{R}^n\text{ for "tensor"}).$$
If this is new, think of the **action** "$g.$" of $g$ as a matrix. Recall that homomorphism ("equal structure") means only 
$$\rho(g\cdot h)=\rho(g)\rho(h)\quad\text{i.e.}\quad (g\cdot h).T=g.(h.T)\;\forall T\in\mathbb{R}^n\tag{*}$$
 where in the first $=$ on the l.h.s. it's $X$'s group operation and on the r.h.s. it's $\text{GL}_n$'s, which is matrix multiplication. I'll write three equivalent sentences in different notations explaining **what an $X$-tensor is**:
1. It's $T\in\mathbb{R}^n$ on which $g\in X$ acts like $g.T$
2. It's $T\in\mathbb{R}^n$ that transforms under $g\in X$ as $g.T$
3. It's an object $T$ that transforms under $g\in X$ like $T\rightarrow g.T$

Note that you can find many such $\rho$ (for one $X$ and one $n$), so which $\rho$ does a physicist mean? This is hidden in some nomenclature and notation, including: the rank, whether the index is up- or downstairs, saying *spinor* instead of tensor. **Examples**:

1. **$X=\text{SO}(3)=\text{rotations in }3\text{ dim.}$, rank 1**: A rank $1$ 3-tensor $\vec{v}\in\mathbb{R}^3$ is an element of the **fundamental rep.** of $\text{SO}(3)$. That's the easiest rep. as $R\in \text{SO}(3)$ acts like (read $\equiv$ as "was defined as" and $:=$ as "is now defined as") $$\rho(R)(v)\equiv R.\vec{v}:=R\vec{v}$$ i.e. by matrix multiplication. (This seemingly tautological definition is worth dwelling on! Is (*) fulfilled? It has to be.)  This is what people in school call **vector**, it's the arrow with the 3 numbers "that rotate into each other,...". All that makes a vector is that he rotates in the fundamental way. All 3-tensors build on this representation, like...
2. **$X=\text{SO}(3)=\text{rotations in }3\text{ dim.}$, rank $k>1$**: A rank $k>1$ 3-tensor extends this behaviour to $k$ indices where every index has to be multiplied by $g=(R_{ij})$, e.g. $T$ is a $k=2$ 3-tensor iff
$$\rho(g)(T)\equiv g.T = g.(T_{ij}):=(R_{ik}R_{jl}T_{kl})\text{  (repeated indices summed from 1..3)}.$$
In this case, $n=3^2=9$ is the dim. of the *2-tensor representation*. If you have read this far, you should definitely check that the single rep. requirement (*) is satisfied for this action! Note that it's purely convenience to arrange $3^2$ numbers in a square matrix. Writing it like $(T_{11},T_{23},T_{13},T_{31},..)$ stays a rank 2 3-tensor if you modify the action of $g$ accordingly. (Why does it stay one? Because ( *) is still satisfied!)
3. **$X=\text{some Lorentz group}$**: different choices of rep. have very different, in general super important, applications in physics. The fundamental rep. (acting in analogy to exp. 1 but in this case $n=4$) consists of *contravariant 4-vectors* $(x^\mu)$ with $\mu=0,..3$ summed in the following (without any signs from metric or so). Another 4d rep. is obtained for a Lorentz trafo $g=\Lambda=(\Lambda^\mu_\nu)$ by $$\rho(g)(x)\equiv g.(x_\mu):=((\Lambda^{-1})_\mu^\nu x_\nu)=\Lambda^{-1T}x$$
(matrix multiplication in last term) dubbed [*dual representation*](https://en.wikipedia.org/wiki/Dual_representation) that contains all **covariant** 4-vectors. Some comments on this:
- Check again (*) if you want or at least check that just $\Lambda^{-1}$ instead of additionally transposing like $\Lambda^{-1T}$ in the last term would **not** furnish a rep. Conversely, just transposing without inverting gives no rep. either!
- The need for transposing $\Lambda$ is why sometimes people refer to **covariant vectors as row vectors**. It's probably not as complex as you think: A *column* vector's entries are summed over with one *row* of the multiplying matrix $\Lambda^{-1}$ and a *row* vector's entries with one *column* of the matrix. Here $\Lambda^{-1}$ is transposed and then multiplied with $x$ by matrix multiplication. So $x$'s entries are summed with each of $\Lambda^{-1}$'s *columns*. Hence the lower index in $(x_\mu)$. The place of the index tells you which rep. the author wants to consider!
- In $\text{SO}(3)$ the dual rep. is literally the same as the fundamental rep. because $\text{SO}(3)\ni R=R^{-1T}$ by def. of $\text{SO}(3)$. So no need to distinguish between upstairs and downstairs indices! There's simply **no difference between covariant and contravariant 3-tensors** of any rank. In the course of writing this, I wondered why not take $$R.\vec{v}:=\vec{v}^TR^T$$ ($R\in \text{SO}(3)$ and matrix multiplication on the right) as the "downstairs index" rep. Fortunately this doesn't work at all - try to write out $S.(R.\vec{v})$ to see this.
4. **$X=\text{some Lorentz group}$**: Lorentz rep. theory [is vast](https://en.wikiversity.org/wiki/Representation_theory_of_the_Lorentz_group)! Have a look at [this subsubsubsection](https://en.wikiversity.org/wiki/Representation_theory_of_the_Lorentz_group#Common_representations) of common reps. for example.

**Upshot:** Whenever the t-word drops, please know that, along the lines, this needs to include two things: a group $X$ and a rep. of it $\rho$.

Let me now answer OP's question,
> What is a tensor?

A tensor is anything that lies in *some* representation of *some* group.

Deducing the transformation law from notation
============================
In real-world physics language, one will hardly ever be given the precise transformation behaviour, i.e. rep., under which a physical quantity transforms. But it is very often understood. Let's exemplify this in special relativity:

We start off with **the** rank 1 4-tensor, $x^\mu$. We know by notation that it's what it is, namely $(t,x,y,z)$, so we deduce its transformation behaviour under a boost $\Lambda$, namely $x^\mu\rightarrow\Lambda^\mu_\nu x^\nu$. The covariant version like $x_\mu\rightarrow(\Lambda^{-1})^\sigma_\mu x_\sigma$. Now a standard question would be "How does $x^\mu x_\mu$ (indices summed 0,..3 without signs) transform under $\Lambda$?". And from the first part of my answer you could be inclined to say "**You** have to tell me how it transforms, don't fool me!". 

But physicists mean something very natural when they write composites of tensors: The known transformation law of the pieces carries over. Every object you write has to have a definite trafo law, to naturally define the trafo of the composite as *transforming each component separately*. The answer to the question would hence be
$$x^\mu x_\mu \rightarrow (\Lambda^\mu_\nu x^\nu)\; ((\Lambda^{-1})^\sigma_\mu x_\sigma) = x^\nu \delta^\sigma_\nu x_\sigma = x^\mu x_\mu.$$
So combining fundamental and dual rep. of the Lorentz group like $x^2:=x^\mu x_\mu$ produces an object transforming in the *trivial representation* (and is hence defined to be a 4-*scalar*).

Soft equivalence to tensors in differential geometry
===================================================
I'll be sloppy about the difference of tensor fields and tensors. Let me also keep this short and only elaborate on where in a rank $(p,q)$ tensor $T$ as defined by $$T=T^{\mu_1\dots\mu_p}_{\nu_1\dots\nu_q}\frac{\partial}{\partial x^{\mu_1}}\dots\frac{\partial}{\partial x^{\mu_p}}dx^{\nu_1}\dots dx^{\nu_q}\in TM^{\otimes p}\otimes T^*M^{\otimes q}$$
one can read off the transformation law. In the above decomposition into coordinates of the implicitly specified chart/coordinate system $x$ on a patch $U\subset M$, the transformation is read off from the definition of the (co)vector fields $\frac{\partial}{\partial x^{\mu}}$ and $dx^{\nu}$. A $(1,0)$ tensor (i.e. a tangent vector) $V$ is defined **independently of a chart** as the derivative along an equivalence class of curves (I won't write out the definition here). So for two different charts $x,y$ we get two different sets of coordinates because
$$V^\nu \frac{\partial}{\partial x^{\nu}}=V=\bar{V}^\mu\frac{\partial}{\partial y^{\mu}}$$ 
which is really a beautiful equation showing why differential geometry is the language in which general relativity has to be formulated. The ingenious way of defining a tangent vector as a directional derivative along a curve gives rise to the object $V$ which is well defined **without specifying a coordinate system**! In GR, we rarely deal with these abstract objects, we always pick a frame and write the coordinates. But keeping in mind that there is an abstract thing from which we derive the coordinates already tells us that it has fulfill the tensor transformation properties because we *calculate* the transformation behaviour and don't *check* it. We calculate it from the above as 
$$\bar{V}^\mu=\frac{\partial y^\mu}{\partial x^{\nu}}V^\nu.$$
Analogously, a covector field transforms with the transpose inverse, 
$$\omega_\nu dx^{\nu}=\omega=\bar{\omega}_\mu dy^{\mu}\quad\Rightarrow\quad\bar{\omega}_\mu=\frac{\partial x^\nu}{\partial y^{\mu}}\omega_\nu.$$
If we put only Lorentz frames in our atlas of $M$, i.e. $\exists\Lambda:\Lambda=(\frac{\partial y^\mu}{\partial x^{\nu}})\;\forall\text{ charts }x,y$ then $V$ lies in the fundamental and $\omega$ in the dual representation of the Lorentz group.

Hence, every tensor in the differential geometry sense indeed lies in some representation of some group (the group of coordinate transformations with the fundamental and dual representation) but I am honestly not sure whether the converse also holds. E.g. the spinor rep. is surely not realisable if $M$ is taken as our spacetime but you might find other $M$ (such as the spin bundle) to realise a spinor as a tangent (co)vector but this is leaving my area of expertise.

Thank you for reading this monstrous answer! :)