I just killed razuvious first try as fury with about 484 gear. nothing special..just save cds for when u get low and dps him hard. brutalus= dpsgear+prot and delaying cooldowns as much as possible.
vashj is easiest just in prot spec, because u dont really have to worry about her getting to 99 stacks. jsut be careful in p3 because she hits hard that way.