The Banach-Tarksi theorem is one of the most notorious "counterintuitive consequences" of choice (and in fact in all of mathematics), making heavy use of non-measurable sets. However, full choice is not needed, and it is well-known that under $ZF$ the Hahn-Banach theorem suffices, which in turn is implied by the ultrafilter lemma. In many cases, it turns out the "pathological" and "counterintuitive" consequences of choice actually follow from much less.
The Partition Principle (implied by $AC$) and even the Weak Partition Principle (if $P$ is a quotient of $S$, $|P| \ngtr |S|$) already imply non-measurable sets. $AC$ implies $PP$ but whether $PP$ implies $AC$ is a long-open problem, so whether this is a strictly weaker principle is unknown, but these statements are to many people so intuitive and unobjectionable that their failure, e.g., "a set can be partitioned into strictly more equivalence classes than it has elements" seems to many people much "worse" than Banach-Tarski. From the Partition Principle or any similar principle is there any known way to prove Banach-Tarski, or a similar result? Is there any known way to get from PP to the Ultrafilter lemma?