We present a general formulation of special relativistic magnetohydrodynamics and derive exact radially self-similar solutions for axisymmetric outflows from strongly magnetized, rotating compact objects. We generalize previous work by including thermal effects and analyze in detail the various forces that guide, accelerate, and collimate the flow. We demonstrate that, under the assumptions of a quasi-steady poloidal magnetic field and of a highly relativistic poloidal velocity, the equations become effectively time independent and the motion can be described as a frozen pulse. We concentrate on trans-Alfvénic solutions and consider outflows that are super-Alfvénic throughout in the companion paper. Our results are applicable to relativistic jets in gamma-ray burst (GRB) sources, active galactic nuclei, and microquasars, but our discussion focuses on GRBs. We envision the outflows in this case to initially consist of a hot and optically thick mixture of baryons, electron-positron pairs, and photons. We show that the flow is at first accelerated thermally but that the bulk of the acceleration is magnetic, with the asymptotic Lorentz factor corresponding to a rough equipartition between the Poynting and kinetic energy fluxes (i.e., ~50% of the injected total energy is converted into baryonic kinetic energy). The electromagnetic forces also strongly collimate the flow, giving rise to an asymptotically cylindrical structure.