Maintenance Plan Takes Too Long - Locks Tables - Indexing To Blame
Why are you rebuilding the indexes? Do you have any evidence that the rebuild is required/needed/beneficial? Have you considered when to use Reorganize vs. Rebuild?

Consider using one of the many index maintenance scripts like the ones from Ola Hallengren or Michelle Ufford. These scrips have intelligence in them to do appropriate maintenance action according to the index fragmentation and will reduce the offline duration by rebuilding only when truly required (hopefully never).

IF a rebuild is needed then there is nothing you can do w/o going to an Enterprise Edition and using online index rebuild.

Oh, one more thing: do not shrink the log. You are only causing it to take more time when it grows back.