10 feet of horizontal separation is required for water mains from drains, storm sewers, sanitary sewers, combined sewers, or sewer connections. This applies for piping installed with no special construction (drains, storm sewers, sanitary sewers, combined sewers, or sewer connections of standard construction).
Fire mains are not addressed in the standard specifications.
However, since both the fire main and potable water main are constucted of water main quality piping (this is considered special construction), you should have no problem installing both of these services in the same trench.
You should install the pipes at least wide enough apart such that you are able to operate a compacting machine between the pipes.