Let's see: $\mathsf{AD}$ implies that all sets of reals are Lebesgue measurable, have the Baire property, and the perfect set property (so, a version of the continuum hypothesis holds). It is conjectured that it also implies that all sets of reals are Ramsey. All these statements fail (badly) in the presence of choice.
(There is a technical strengthening of $\mathsf{AD}$ known as $\mathsf{AD}^+$ that implies that all sets of reals are Ramsey. It is open whether $\mathsf{AD}$ and this strengthening are actually equivalent.)
$\mathsf{AD}$ implies that there are no nonprincipal ultrafilters on the natural numbers. This in turn has as a corollary that every ultrafilter is $\omega_1$-complete. It is this way that the first truly dramatic consequences of determinacy were established:
Solovay showed that $\omega_1$ is measurable, and in fact the club filter on $\omega_1$ is an ultrafilter. Also, $\omega_2$ is measurable, and the restriction of the club filter to sets of cofinality $\omega$ is an $\omega_2$-complete ultrafilter. Same with cofinality $\omega_1$. On the other hand, $\omega_3,\omega_4,\dots$ are not measurable, in fact they are not even regular but have cofinality $\omega_2$. The next regular cardinal is $\omega_{\omega+1}$ which, again, is measurable. It is conjectured that the cofinality function on successor cardinals is nondecreasing below $\Theta$ under $\mathsf{AD}$. Here, $\Theta$ is the supremum of the ordinals that $\mathbb R$ can be mapped onto. Under choice, $\Theta$ is just $\mathfrak c^+$ which, under the continuum hypothesis and choice, is just $\omega_2$. However, here $\Theta$ is a large cardinal. (So, a version of the continuum hypothesis fails.)
Work from Steel and Woodin shows that, if we restrict our attention to $L(\mathbb R)$ (which is an inner model of determinacy if we assume $\mathsf{AD}$ in $V$), then every regular cardinal below $\Theta$ is measurable. This result of Steel and Woodin holds in much more generality than in $L(\mathbb R)$, but the precise statement and the arguments become rather technical. Here, one should also mention Moschovakis's covering lemma. The softest version of it is already significant: If there is a surjection from $\mathbb R$ onto an ordinal $\alpha$, then there is also a surjection from $\mathbb R$ onto $\mathcal P(\alpha)$.
A recent result of Woodin is that every cardinal below $\Theta$ is in a sense of large cardinal character. More precisely, it is Jónsson, or stronger. Again, this is easier to prove under the assumption that $V=L(\mathbb R)$, but holds in full generality. The argument can be seen in this recent preprint in the ArxiV.
The precise pattern of Jónsson cardinals under determinacy is still under investigation, but a nice place to start is the book
Eugene Kleinberg. Infinitary combinatorics and the axiom of determinateness, Lecture Notes in Mathematics 612, Springer-Verlag, Berlin-New York, 1977. MR0479903 (58 #109).
Kleinberg realized that the regular cardinals under determinacy are controlled by partition properties, and the size of certain ultrapowers. This proved key for many results that followed. Moreover, the investigation of infinite exponent partition relations became an important part of the combinatorics of $\mathsf{AD}$. Under choice every infinite exponent relation fails.
The study of non-well-orderable cardinals under $\mathsf{AD}$ is just starting, but there are already significant results, showing that many complicated partial orders can be embedded into the ordering of these cardinals. For example, in
W. Hugh Woodin. The cardinals below $|[\omega_1]^{<\omega_1}|$. Ann. Pure Appl. Logic 140 (1-3), (2006), 161–232. MR2224057 (2007k:03136),
Woodin shows that (in the theory $\mathsf{AD}(\mathbb R)+\mathsf{DC}$) one can find $\Theta$-decreasing sequences, or $\Theta$ many incomparable cardinals, and much more. Here, $\mathsf{AD}(\mathbb R)$ is the strengthening of determinacy where we allow real (rather than integer) moves in our games. In another direction, we have that under determinacy $\mathbb R$ and $\omega_1$ have incomparable cardinalities, and they are both successors of $\omega$. And the cardinality of $\mathbb R$ has several cardinal successors, one of which is the quotient $\mathbb R/\mathbb Q$, where two reals are identified iff their difference is rational. Yes: A quotient has larger size than the original set. See here for more on this.
I'll stop here, but what I've mentioned is really just scratching the surface. You may want to look at chapter 6 of Kanamori's book for more information, or at the beginning of my paper with Richard Ketchersid on a trichotomy result for additional, recent results, and some details on $\mathsf{AD}^+$.
The above being said, in the comments Douglas Zare points out that whether some of these consequences seem unintuitive depends on whether we consider choice and its consequences intuitive or not. Actually, if we are agnostic about $\mathsf{AC}$, many consequences of $\mathsf{AD}$ are natural. The idea is that the sets of reals in an $\mathsf{AD}$ model provide us with a natural class of "definable" sets, extending definability classes such as those coming from the interplay of logic and analysis (Borel or $\Delta^1_1$, projective or $\Sigma^1_n$, etc). A recent theme is that certain properties of simply definable sets of reals provable in $\mathsf{ZF}+\mathsf{DC}_{\mathbb R}$, extend to all sets of reals under determinacy. The pattern of uniformization for projective sets is a classical example of this. A striking recent development in descriptive set theory, due to Ben Miller, is that most classical dichotomy theorems in descriptive set theory are soft consequences of graph-theoretic dichotomies via Baire category arguments, see
Benjamin Miller. The graph-theoretic approach to descriptive set theory. Bulletin of Symbolic Logic, 18 (4), (2012), 554-575.
Extending the work mentioned above, Richard Ketchersid and I have shown that these graph theoretic dichotomies hold for arbitrary sets of reals under $\mathsf{AD}^+$, and therefore we have the classical dichotomies in the $\mathsf{AD}$ context without any restrictions in the complexity of the sets involved. (In fact, we have versions that apply to all sets in $L(\mathcal P(\mathbb R))$, not just to sets of reals.) Andrew Marks's answer points to some of these dichotomies. For more, see here.
