I would recommend asking them for their implementation project plan and how they plan to implement you guys.
The Sure Step methodology is good, but sometimes, experienced partners will have their own way of implementing that is more efficient and have a greater success rate.
If their implementation plan doesn't feel right, then you can ask them to follow the Sure Step methodology or develope a hybrid of it.