To add - having ANY animals, but especially when you are talking large animals, and being part of the military neccessitates having a solid Plan B and C for the care and keeping of those animals if/when orders come through that are contrary to what you expected (ie OCUNUS, etc). For a horse, this (to me) means having a plan for where you will board the horse if/when the situation arises in which you will not be able to take the horse with you either immediatley or for the duration of the time. Whether this is a formal boarding facility or if you are fortunate enough to have family with the facilities to maintain the horse for you - and to also be sure you are allowing for this cost in your budgetary planning.
We were very careful about our accumulation of animals during my husbands AD time for just this reason. We were mindful of the limitations of small household pets (housing is generally two "domestics" - though this varies by base and whether it is base housing or PPV housing, rentals are a crap shoot you may find someone willing to rent to more or you may find no pet friendly housing options on the rental market) during the time that we were living in base housing and private rentals and we only accumulated our large animals and additional domestic pets once we had purchased our home/land and knew that if/when he PCSd (Plan A was to stay here for the duration of his career - but we had Plan B) we would likley split households for that last tour (he was nearing the end of his career at that point) rather than attempt to relocate with all our animals and re-homing was not an option for us. As it happened, Plan B had to go into effect because he did get orders to PCS and we did split households with myself and the children staying here with the dogs, cats and horses and my husband moving on without us for the last three years of his AD time. Was it optimal, no - did it work for us, yes. It was what we had to do - not only for the animal reasons, but also because we had a house to consider in a market where real estate was NOT moving and renting was not an option due to our financing having a residential occupancy clause.
It is not at all impossible to have horses and be a military member/family - it just takes careful planning and forethought.