Environmental monitoring is a typical Internet of Things (IoT) application. Environmental monitoring plays a significant role, for example, in smart farming and smart city applications. Environmental magnitudes are usually measured using wireless sensor nodes, which are often battery-powered, and the number of sensing nodes can be large. One effective method for reducing the energy consumption of a sensor node is to use data compression to reduce the amount of data required for transmission via a wireless connection. Compressing the sensor data means fewer transmission periods, and thus, lower energy consumption. Compression methods should be effective for compressing environmental magnitudes and be computationally light to be suitable for constrained sensor nodes. A compression algorithm should be able to compress an online data stream. In this paper, we review some compression algorithms suitable for environmental monitoring and present two new versions of those algorithms. The algorithms were evaluated, tested, and compared. The main parameters used for the comparisons were compression ratio, root mean square error, and inherent latency. The simulation results obtained using real datasets demonstrate that simple linearity-based compression algorithms are effective and suitable for compressing environmental data. Two new compression algorithm versions proved to be effective for compressing sensor data with reasonable compression quality and predictable inherent latency.