In my limited experience with Bromoil, I've used David Lewis' Bromoil paper (available thru Photograpers Formulary), and J&C Bromoprint ( thru J&C but probably available from one of their European partners). Both papers have an un-hardened surface that lends itself well to Bromoil, hand-painting, etc..
The nicest paper (although not a bromoil paper) I have used is agfa multicontrast matte. This paper has a beautiful surface, capable of exquisite detail. Unfortunatly its no longer made, but still can be found I hear.
David Lewis http://www.bromoil.com/ also makes an excellent paper for bromoiling. he also manufactures the nicest inks and brushes I have been able to find.
Almost any photo paper can be used for bromoiling. I have used many modern papers. The trick is to find the right time/temperature soaking for the paper. once you hit on it, most papers will ink up well. Bromoil papers will generally ink more easily and require lower soaking temperatures. I would recommend starting with them and working into modern papers once you have some experience.
You should really check out David Lewis' paper. It has qualities similar to the early Zone VI Brilliant. Works nicely for silver prints, but especially well for Bromoil.
I did a lot of contacting printing on it with large format negs and got great detail and tonality (unusual for Bromoil) - particulary with the Fitch brush that David sells.
I used to get the paper either from Photo Formulary or David's site.
Tom
That's good to hear. If I'm not mistaken this paper has actually been called comparable to the old Agfa MCC 118, and is now officially on my list to try.