Unless given special movement logic (unlikely and probably not worth it I'd guess) giving AI fortresses move speed just results in them eventually drifting over to be in range of whatever wormhole you're using, reducing your options without really being interesting. I don't remember exactly when they became static like they are now, but that's why that happened.
I would say basically make the changes originally posted. Make them less effective in general to give other ships a chance, but make them more effective against bombers and other polycrystal stuff so they aren't such a hard counter. The AI version's HP could use a little reduction, but that's not as big a deal.
Zoutzakje's idea making the AI versions some could be interesting too.
EDIT: How about this for a first "pass" of this concept?
Either the number of shot per salvo or the damage per bullet should be halved (but not both), polycrystal multiplier increased from .01 -> .25
That may be a bit high for the polycrystal multiplier though.
Remember you're effectively removing armor effects when you boost the polycrystal multiplier like that. Mk2 and above bombers are getting 80% armor reduction right now, so half damage and a .25 polycrystal multiplier would be in the 60x to 62.5x increased damage vs bombers range rather than around a 12.5x increase. Note that the in game reference is showing mk3 forts doing 3306 damage per shot against bombers and 3906 against bomber starships before armor rather than the 4000 I expected, which makes no sense so I'm not sure I trust it that mk2 bombers are getting 80% reduction against mk3 forts. Either way, giving fortresses 5k armor piercing to be able to ignore the 4800 armor of mk4 bombers might make more sense as a first step, and then increase the multiplier if that's still not enough damage. Or maybe 2.4k -> 4.8k armor piercing for mk1 -> mk3 forts.
I'm not quite sure what role you're hoping AI fortresses will play though. Currently they more or less prevent you from using non-polycrystal stuff around them until you kill them, which at least forces you to pay some attention to them when making attack plans. They're just really really boring to remove. Playing with the damage seems like it would just change how much it costs to remove, and possibly whether you throw the entire fleet at them or just the bombers/polycrystal stuff, which doesn't seem like it would make them more interesting. If you just want them to be less boring to get rid of, reducing health while increasing their polycrystal bonus by about the same factor as you reduce their health by would do it.
So maybe 1/3 of current health, 0.03 vs polycrystal, 5k armor piercing? Would do about 5x as much total damage to bombers compared to currently just from the armor piercing, which is probably fine. The mk3 forts under 2 core forcefields I'm seeing at AI home command centers would be more of a pain to deal with (since core FFs don't reduce damage and that's over 400 million hp of FFs before hitting the fort if they spawn next to it), but that might be tolerable even with just the base game since that is just on the AI home planets. Do be careful if drastically increasing damage to bombers that forts don't become a real pain to remove without golems or other expansion stuff. Removing the EMP immunity and making them immune to repair would at least make EMPs or multiple assaults viable, though the fortress baron AI would be really painful if those were your best options. Are you thinking of applying this stuff to superfortresses too or just leaving them alone to make them different? I'd be even more careful with adjusting damage on those since they have so much range.
