This isn't an answer to the question in the last paragraph, but here's one way to repair your intuition about applications of the axiom of choice. One way to think about why choice is not intuitive is to think in terms of computational resources (see, for example, this blog post by Terence Tao). For any kind of mathematical construction you might want to do, think about what kind of computational resources you'd need to actually carry it out. Some sets have the property that it takes a lot of computational resources to write down an element of that set. For example, the set of solutions to a Diophantine equation may be non-empty, but it may still take a long time to actually write one down.
Whenever you have a bounded amount of computational resources, the axiom of choice is going to be false because you'll run out of computational resources when you try to write down an element of a sufficiently large product of non-empty sets. For example, suppose you have only a finite amount of computational resources. Then the axiom of countable choice will be false: if I take countably many Diophantine equations, none of which you currently know solutions to, and ask you to write down a solution to each, you may not be able to do it even if I guarantee to you that solutions exist because it may take you an infinite amount of computational resources, which you don't have. (Of course, you may be able to cleverly solve them all at once, but I may be able to stump you with an even trickier set of Diophantine equations. Matiyasevich's theorem shows that I can just ask you to write down the solutions to every Diophantine equation.)
You can think about algebraic closures and maximal ideals similarly. When you actually try to construct the algebraic closure of a field, you need to repeatedly find irreducible polynomials so you can adjoin their roots and get a bigger algebraic extension. It takes computational resources to find irreducible polynomials, depending on the nature of the field you started with, and if the field you started with is sufficiently complicated it may take more computational resources than you have. Similarly, when you actually try to write down a maximal ideal containing an ideal, you need to repeatedly find elements not contained in the ideal but that do not, together with the ideal, generate the unit ideal. It takes computational resources to do this, etc.