When I first had a dabble at 5x4, I was also a bit underwhelmed and effectively gave up on it prematurely. However, being brutally honest with myself, I suspect it was more about the way I'd shot it the film than the medium itself.
I've seen photos 5x4 that have been produced by Leon, Paul Mitchell and many others on FW - using a variety of film, including FP4+ and HP5+ and the quality of the end result is breathtaking. I can only surmise that it's just a matter of getting the combination of light, exposure and processing / printing method in balance.
I'm not trying to be glib or in any way critical but I doubt that simply swapping films will make the difference. Like yourself, I'm currently much more comfortable with MF but I'm about to step put of that comfort zone and see if I can make 5x4 work for me with HP5+ and New Type 55.