First let me tackle the case of ordinals, with and without choice, then we can move on to non-well-orderable sets.
For the $\aleph$ numbers
The situation here is somewhat similar with and without choice, with a few minor points which diverge. First of all, the least $\lambda$ exists because as you point out $\kappa<2^{\kappa}$, so the class of ordinals satisfying $\kappa\leq2^\lambda$ is not empty, so there is a least one.
Easton's theorem, mentioned in an earlier answer, shows that if we start with $\sf GCH$, i.e. $2^\kappa=\kappa^+$ for all infinite $\kappa$, then any "reasonable function" can define the continuum function for regular cardinals in some extension of the universe which did not change cofinalities.
In Easton's construction we only talk about regular cardinals, not singular cardinals. And the singular cardinals in his construction take "the least possible value". For singular cardinals with uncountable cofinality, Silver showed that the behavior of the continuum function is dictated by the behavior below it "on a reasonably large set of points", but we can also prove that this reasonably large set can be taken to only contain singular cardinals with countable cofinality.
Shelah, Magidor, Gitik, Woodin, and many others showed that for cardinals with countable cofinality there's some we can say, but not a whole lot. For example, it is consistent that $\sf GCH$ holds below $\aleph_\omega$, and $2^{\aleph_\omega}=\aleph_{\alpha+1}$ where $\alpha$ is any (infinite) countable ordinal. But we don't know if it is possible for $\alpha$ to be $\omega_1$, for example. So it is hard to say what is the least $\lambda$ such that $2^\lambda\geq\aleph_{\omega_1}$ if we assume that $2^{\aleph_n}=\aleph_{n+1}$ for all $n<\omega$.
In general, the easy answer to your question, is we can't say anything for a given $\lambda$, since we can always push $2^{\aleph_0}$ to be at least as large as $\lambda$. It gets trickier if you define $\lambda$ in non-absolute terms, e.g. taking $\lambda=(2^{\aleph_0})^+$, so the meaning of $\lambda$ changes between models. But even then you can't say a whole lot more, because it's possible to have $2^{\aleph_0}=\lambda$ and for some uncountable and regular $\mu<\lambda$ make $2^\mu=\lambda^+$.
Without choice, though?
Well, if we assume the axiom of choice fails, then we can prove that there is a least $\kappa$ such that $2^\kappa$ is not an $\aleph$ anymore, in which case the $\leq$ immediately becomes $<$ for further cardinals. But we can also differentiate between "There is an injection from $\kappa$ into $2^\lambda$" and "There is a surjection from $2^\lambda$ onto $\kappa$". And those two are very different things.
The paper mentioned of Fernengel and Koepke deals with the surjections. There they show that pretty much the only restriction is that you need these to not decrease with the increase of $\lambda$. There's no requirement even on the cofinality. But they do not deal with the injection case.
When I was visiting Bonn a few years ago, I pointed out that it is possible to modify the construction to get some information also on the least $\kappa$ such that $\kappa\nleq2^\lambda$. Although here, since they do not use large cardinals and in fact their construction preserves cofinalities, we have more restrictions on what we can and cannot do. Of course, if you want to allow large cardinals in the mix, the whole things becomes significantly more complicated, and probably you can do almost anything as well.
But other than these small observations, the same things as before still hold. After all, just assuming choice fails does not tell us where in the universe it fails.
For arbitrary cardinals
Well, what about sets which cannot be well-ordered, then? That's a huge mess. First of all, you need to ask yourself what does "smallest" even mean? If there is a notion of "smallest" that means that the cardinals are well-ordered and choice holds.
So without choice you need to contend with the fact that there is no smallest. For example, if $A$ is amorphous, its power set is also Dedekind-finite. That means that if $B\subsetneq A$, then $2^B<2^A$, since $\mathcal P(B)\subsetneq\mathcal P(A)$.
But since either $B$ is finite, or $A\setminus B$ is finite, it is easy to show that $A<2^B$ for any infinite subset of an amorphous set (map $B$ to its singletons, and there are only finitely many points missing, which we can map to finitely many pairs, for example).
Also, you can't quite mix things here. If $A$ is amorphous, then it cannot be linearly ordered. But power sets of ordinals can always be linearly ordered. So there is no ordinal $\lambda$ such that $A\leq 2^\lambda$ to begin with. In the other direction, as remarked, $A$ has a Dedekind-finite power set, and so $\aleph_0\nleq 2^A$.
On the other hand, suppose that $A$ is an $\aleph_1$-amorphous set, namely every subset is countable or co-countable, and in a non-trivial way so every infinite subset of $A$ is Dedekind-infinite as well. In that case we can easily show that if $B\subseteq A$, then either $|A|=|B|$ or $|B|\leq\aleph_0$. But what can we say, in that case, about power sets? Not much, not much at all. We can't even say that $2^{\aleph_0}<2^A$ without additional assumptions.
The situation is in fact much worse without choice since we don't even understand how to control power sets of arbitrary sets in $\sf ZF$. We have no good understanding of forcing like a (generalised) Cohen forcing which does not add "bounded subsets", or even what it means for a cardinal to be regular or singular. The whole structure just immediately... breaks down.
In fact, even for $\aleph$ numbers if we wish to preserve the failure of the axiom of choice, then there is no forcing which is guaranteed to (1) add subsets to $\kappa$ without adding bounded sets, and (2) not make $2^\lambda$ well-orderable for any $\lambda<\kappa$. The only exception , of course, is $\kappa=\omega$, where we have Cohen reals to do the trick, mainly because finite sets have finite power sets anyway. (Things work out if $\operatorname{Add}(\kappa,1)$ is well-orderable, which is the same as saying that $\kappa^{<\kappa}$ can be well-ordered. But of course, that will fail at some point if the axiom of choice fails.)
In conclusion!
We can't say a whole lot. Sorry. And we can say even less if we want the axiom of choice to fail. And we can say a lot less if we want to focus on sets which cannot be well-ordered.
Yes, no, and consequently also no.
The first one is actually a theorem: if there is an infinite Dedekind-finite set, then there is one which can be mapped onto a strictly larger set. That means that the surjection defines the partition you are looking for.
Suppose that $A$ is Dedekind-finite, then $S_{inj}(A)$, which is the set of all injective finite sequences from $A$, is also Dedekind-finite. For if it wasn't, then we would have a countably infinite set of enumerated finite sets, and their union is therefore a countably infinite subset of $A$, and that is impossible.
Now take, for example $S_{inj}(A)$ without the empty sequence. Then the function erasing the first coordinate from each non-empty sequence is surjective onto $S_{inj}(A)$. Indeed, taking any subset which contains "all sequences of length $n\in I$" for some fixed infinite $I\subseteq\omega$ will work in a similar way.
For the second question, note that if $A$ is amorphous and $f\colon A\to X$ is surjective, then $X$ must be amorphous (or finite, if you'd like to require that amorphous implies infinite). For otherwise, simply partition $X$ into two infinite subsets and look at their preimages, both would have to be infinite subsets of $A$ which are disjoint.
How does that help us? Well, if $X$ is infinite, then the preimage of each point is finite. Now, starting with some $x\in X\setminus A$, consider $f^{-1}(x)=A_0$, then $f^{-1}(A_0)=A_1$ is also finite, and it must be distinct from $A_0$, and then we can continue by recursion and define a countably family of finite subsets of $A$. But this is impossible as the power set of an amorphous set is itself Dedekind-finite.
Note, however, that if $X$ is amorphous, its partitions are either finite; almost all singletons; or incomparable with $X$ itself. So we can get a partition that is incomparable, just not a partition that is strictly bigger.
Best Answer
Yes, these sets can exist for all infinite well-ordered cardinals. The construction is essentially the same type. We can even have $\sf DC_{<\operatorname{cf}(\kappa)}$ along with a $\kappa$-amorphous set.
For $\aleph_1$-amorphous sets, those can be linearly ordered. In fact, there can be such a set of reals.
The reason the usual proof doesn't work is that there are different linear orders which are uncountable but every proper initial segment is countable (e.g. $\omega_1$, or $\omega_1\times\Bbb Q$ or $\omega_1\times\Bbb Q\times\Bbb Z$, etc.) which means that the usual proof that relies on "$\Bbb N$ is the unique linear order without a maximal element in which every proper initial segment is finite" does not translate to a general one.
And as for comparability, we can arrange that for every $\kappa$ there is a proper class of pairwise incomparable $\kappa$-amorphous sets. How's that on for size? The idea is relatively simple:
First consider a symmetric extension where we added a $\kappa$-amorphous set for some $\kappa$, let's say using Cohen subsets of some regular cardinal $\lambda$.
Now fix a coding of pairs $(\xi,\zeta)$ of ordinals. In the $\alpha$th stage, if $\aleph_\alpha$ is a regular cardinal, take $\kappa=\aleph_\xi$ and $\lambda=\aleph_\alpha$, and this is our symmetric system. Now take an Easton support product of these forcings, and by genericity argument two amorphous sets coming from different symmetric systems must be incomparable.
(What's clever is that you can use a finite support product and still preserve $\sf ZF$ in the outcome model, at least if you've chosen the obvious symmetric system in the first step above.)