The patches will download automatically before you get a chance to play FFXI for the first time. You cannot play without the patches.

Yes it works fine with 56k, as it was made to be capped at that level. Although, the benefit of broadband is downloading the patches faster.