The required temperature depends on the mass of the particles you're considering. You could say photons are always relativistic, so even the photon gas that is the cosmic microwave background is relativistic at 2.7 K. But you're presumably more interested in massive particles.
If you apply the kinetic theory of gases to hydrogen, you'll find that the average kinetic energy will reach relativistic levels (taken to be when it becomes comparable to the rest mass energy) around 10^12 K. For the free electrons (since we'll be dealing with plasmas at any sort of relativistic temperatures), this temperature is around 10^9 K due to the smaller mass of the electron. These temperatures are reached at the cores of newly-formed neutron stars (~10^12 K) [1] and the accretion disks of stellar-mass black holes (~10^9 K) [2], but not at the cores of typical stars. Regarding time dilation, an individual particle's clock would tick slower from the perspective of an observer in the center-of-mass frame of the relativistic gas, but I don't think this would have any noticeable effect on any of the bulk properties of the gas (except for the decay of any unstable particles). Length contraction would probably affect collision cross-sections, though I haven't done any calculations for this to say anything specific. One important effect would be the fact that the distribution of speeds would follow a Maxwell–Jüttner distribution instead of a Maxwell-Boltzmann distribution, and that collisions between particles could be energetic enough to create particle-antiparticle pairs. This would affect things like the number of particles in the gas, the relationship between temperature and pressure, the specific heat of the gas, etc.
You mention the early history of the Universe in your other comment. You can look through this table on Wikipedia to see the temperature range during each of the epochs of the early Universe, as well as a description of what happened. The temperatures become non-relativistic for electrons at some point during the photon epoch.
I suspect you may be misunderstanding time dilation. From the perspective of a particle, time always passes by at 1 second per second. If you yourself were to travel at relativistic speeds (relative to, say, Earth) your perspective of time wouldn't change at all. However, observers on Earth would see your "clock" to tick slower. That is, anything you do would progress more slowly from their perspective. In the very early Universe, a given particle would see most other particles moving at relativistic speeds, and so would see their "clocks" tick slower. These sorts of relativistic effects would influence interactions between particles during collisions, decay rates, etc, but are all things we know how to take into account in our models of the early Universe.
Is there a temperature so hot that relativistic effects are noticeable?