Good science question! It’s because of upthrust (also called buoyancy). You may have heard of a guy called Archimedes (he yelled “Eureka” when he got in the bath once), he discovered a law of physics that we now call Archimedes principle, this law is:
Any object, completely or partly put in fluid, is buoyed up by a force equal to the weight of the fluid displaced by the object.
What this means is when you put the brick in the water it takes up space that previously had water there (if you put a brick in a bucket of water the water level will rise slightly because the water has to go somewhere), this water has been ‘displaced’ by the brick. The volume of the water that has been displaced is the same as the volume of the brick. We know how much that bit of water weighs because we know how dense water is (density is a measure of how close together the molecules in something are).
What Archimedes found out was that the weight of this bit of water was the same as the force that the water makes on the brick to push it upwards. Above water, or in the air the same thing is happening, but this time the brick is displacing air, not water. The bit of air it displaces has the same volume as the bit of water from before, but it is much less dense (molecules in air are much further apart than molecules in water) so the bit of air weighs much less than the bit of water from before.
Like Archimedes said the upward force is equal to the weight, so because the water displaced weighs more than the air displaced above water the upwards force from water is bigger than the upwards force from air. So if you hold the brick in water there is a bigger upwards force from the water helping you hold it up so it feels lighter. When you hold it above water the upwards force from the air is smaller so it’s not helping you as much so the brick feels heavier.
I call it research, when I'm not sure what I'm doing...!