I think jet2 would be a good addition into BHX as they provide a good mix of flights, and as you say they have staying power to make routes work.
Easyjet would also be good for BHX but it just depends on how BHX plays its cards on courting new airlines. They seem too scared incase FR pull out, but the management seem to short sighted to see that booting FR would be a good thing for them.