Aida and linen are like lions and tigers: both cats, but not at all the same.
I've used Aida, linen and other sorts of evenweave fabrics. At the moment I'm using 25ct Dublin linen for my HAED, but it's not for the faint-hearted. Linen has a mind of its own, although I'm enjoying using it. You will be stitching over 1 thread for an HAED on linen. I use a magnifier!
Lots of people use lugana 25ct for HAED. It also happens to be my favourite fabric in the world, but that's by-the-by. The holes are, I think, very clear even at this high count. the threads are also all the same size -- no thick ones or thin ones -- and no slubs, of course. You might want to have a look at that fabric while you are still choosing.