(Abridged) We report on 8.7 and 7.6 yr of RXTE observations of the Anomalous X-ray Pulsars (AXPs) RXS J170849.0-400910 and 1E 1841-045, respectively. These observations, part of a larger RXTE AXP monitoring program, have allowed us to study the long-term timing, pulsed flux, and pulse profile evolution of these objects. We report on four new glitches, one from RXS J170849.0-400910 and three from 1E 1841-045. With nearly all known persistent AXPs now seen to glitch, such behavior is clearly generic to this source class. We show that in terms of fractional frequency change, AXPs are among the most actively glitching neutron stars. However, in terms of absolute glitch amplitude, AXP glitches are unremarkable. We show that the largest AXP glitches observed thus far have recoveries that are unusual among those of radio pulsar glitches, with the combination of recovery time scale and fraction yielding changes in spin-down rates following the glitch similar to, or larger than, the long-term average. We also observed a large long-term fractional increase in the magnitude of the spin-down rate of 1E 1841-045 following its largest glitch. These observations are challenging to interpret in standard glitch models, as is the frequent occurence of large glitches given AXPs' high measured temperatures. We speculate that the stellar core may be involved in the largest AXP glitches. Furthermore, we show that AXP glitches appear to fall in two classes: radiatively loud and radiatively quiet. The latter, of which the glitches of J170849.0-400910 and 1E 1841-045 are examples, show little evidence for an accompanying radiative event. We also show, however, that pulse profile and pulsed flux changes are common in these AXPs, but do not apprear closely correlated with any timing behavior.

48 pages, 17 figures, 8 tables, To be published in ApJ (accepted)