A* is not a hard algo to understand and it is one you should get intimately familiar with if you plan on using it in games.
What you really need from your description is an annotated pathfinder. (clearance based) There is a great description of one here.
This article describes a hierarchical annotated a* path finder however once you can write your own A* from scratch adding features you need for each project is very simple.
Heavy use of a profiler will help you optimize your path finding in short order. It really is a simple piece of code once you get the hang of it.
Edit: I am sorry I forgot to add. If you already have a fast a* the modification to add the clearance based checks is pretty simple. Obviously your base object that anything that is going to use the path finder is derived from needs a "clearance" variable of some kind.
Inside the actually path finder just find the spot where it is checking against if things are walkable or not and that is where you add in the clearance checks. Also when you first generate your map you need to add a var to the node or however your graphing your map to pre-calculate the clearance values.(that will make it faster) Really that is basically all there is to it.