Definitely there would be relative curved motion 'coz the times of flight may be different. After one body comes to rest, the other continues its motion which is definitely curved!!
And also if they are projected one along z-axis and the other along x-axis, one wud absolutely find the relative motion to be curved.
If the case is only 2D, then while they are in motion,
horizontal motion:Both of them are moving with constant velocities and so the relative motion is linear
vertical motion : Both of them are movin' under the same accelaration .So in this direction, the relative motion would be linear
Now, when both the horizontal and vertical motion appear to be linear, the resultant motion wud also appear linear!!
~Cheerio!!!