Bom Dia José Roberto
1º - Acredito que SP tenha a mesma regra do RS que quando tomador do serviço(pagador frete) e prestador de serviço(Transportador) serem inscritos no estado de SP o frete é ISENTO.
2º - Nas demais operações onde incidir ICMS, você deve considerar o ICMS dentro do seu custo de prestação de serviço. Enfim você destaca o ICMS no conhecimento, teu cliente pagará o ICMS por ele estar embutido no preço da prestação e você faz a sua apuração de ICMS no final do mês, se der saldo devedor, emite a guia do referido imposto e paga.
3º - pesquisa na internet por "tabela interestadual de ICMS" deve aparecer uma tabela com operações origem x destino e sua referida alíquota.