Lets collect your thoughts....
The spray foam is a really expensive idea....and for a block home is not cost effective. You need to get as much insulation board on the outside as possible. The less separations between a piece of wood and the styrofoam board and joints the better. The issue is also with your window flange depths, soffit, and rake boards. The more you build out from the existing wall...the more issues you deal with. The contractor with the 2x4 deal sounds like the better idea, if it will fit. The firring strips will hold, but not as well.
There are also vertical sidings with insulation inside which will need less nailing strips attached to the block, assuming you have 8 foot walls.
Go see some of their work and talk to past clients...that is what I always do for my customers.
And remember...it's vinyl siding and really easy to repair anything underneath.