I currently am working with a story set in our world, but in the future, when humans have expanded throughout our solar system, and have just begun to explore and document our galaxy. In this search, the first 'human contact' reveals a species who, by just existing, force humans to redefine what they even define as consciousness. How do I describe something like this.
Start with why. Why does it make them redefine what is consciousness? What drives them to question this? Are you sure that consciousness is the correct term you want to use? As of now, most humans even in the real word can imagine quite a bit in this area. Even things like out-of-body experience are becoming more mainstream. We already acknowledge mental powers (such as telekinesis and telepathy) at the very least in the fantasy world. Warriors and even modern day soldiers are trained to sleep with one eye open. So the term consciousness seems off to me as humans already have a fairly active imagination in this realm even without the sci-fi thrown in.
However, with that being said, to have your characters describe something they do not know or understand is also the very core of science/research/exploration to begin with. Humans relate what they do not know to what they do know. The stars were once thought of as the heavens and gods in the skies because that was the only explanation for how it came to be.
New animals that have never been seen before were compared to other animals to try and categorize and figure out what it is. If you saw an animal with large pincers and a hard shell, you are already imagining a crab even though this animal is not.
So approach it from an explorer/researcher mentality. Have them start describing it.
"It's like I can feel everything and nothing all at once. I can feel the planet, how alive it is. When I breathe, it's like the planet breathes with me as if we are all connected as one but yet we are not."
What it seems more so is that you haven't defined WHAT that difference is yourself. It may not be an issue of how to describe it, but rather, you may not have it defined well enough for you to describe it. Once you know what it is, it should be fairly easy to have your characters relate it to what they know as they experience this new consciousness.
Humans already experience things that are part of existence, but that we do not understand.
Draw from those for a start:
Perhaps : Identify (and/or researching online) legitimate human experiences that are on the very fringe of how we experience ourselves in the universe. This may derive from certain hallucinatory states, transcendentalism, near death, and other altered states of consciousness. Or, it may derive from physical extremes - What it feels like to be hit by a lightning bolt, for example.
Then, build something (your aliens) that is reminiscent of commonalities in those experiences, but unique in some fashion. Perhaps it is something expansive and terrifying, or electrifying and trippy. I recommend building something that the audience says 'Yeah, that sounds like it could be legit,' and then taking it in a new direction, bigger, stranger, unusual. I suspect the result will be that the audience will understand that this is a very alien being that they are now learning about.
Add on to this with the senses, (play with it), if this species has unusual odor, unusual frequencies through which they communicate, unusual ... textures? This can add to the bizarre otherness of them.
I suspect the more research (online or at the library) that you do on what the bizarre fringes of human experience contain, the more of an idea you will begin to flesh out that will inform your species. It can potentially feel recognizable, but also alien, to the reader.
The above is to provide ideas about what might make an alien species weird, and difficult to understand.
But you asked more directly about your characters failing to understand the aliens:
Your characters can fail to understand it for any number of reasons. Perhaps they only experience one part of the aliens' manifestation - They only hear it, or smell it, or perceive it in a ... strange way, they get the heeby-jeebies when it is nearby or some such. It communicates with them through technology but they cannot find it in the physical universe. It is dark matter. Etc. I suspect it is best if the reader has a handle on what the aliens are, even if the characters do not comprehend it, but that is up to you. (Characters failing to understand things in stories... is common.)
What makes something feel truly alien and incomprehensible? It's the experience of trying to figure it out and failing. In his masterwork, Dhalgren, Samuel Delany poses a number of puzzles for his main character to figure out --mysteries that defy explanation. Throughout the book, the protagonist works his way towards the answers, but just when he thinks he's on the verge of a rational explanation, he learns something new that completely invalidates his theories (the same experience awaits the reader who tries to fit all the book's events into a single, linear, consistent narrative). Other authors that productively mine similar territory include Philip K. Dick (Do Androids Dream of Electric Sheep), Lewis Carroll (Sylvie and Bruno) and Haruki Murakami (The Wind-up Bird Chronicles).
People try to figure things out, it's what we do, and if you can conceive of something, so can the reader. So how do you write about something you can't conceive of? Lean into the mystery. Give your characters a puzzle to solve, and just when they think they have it figured out, throw in some incompatible data.
However, it's clearly a dangerous game to play. If you do it poorly, the story feels either poorly cobbled together, or like a blatant cheat. I think the reason it works for each of the authors above is that what they are really interested in is the characters, and how they respond to the stress of uncertainty. So the mystery is the means to explore the characters, not the other way around.
One way that might help in part is to ensure that the species makes no sense to us. As an example see this response. This is a story I remember reading many years ago.
It involves (as far as I can remember) an enormous creature of continental size that arrives one day from outer space and lands on Earth. It's very disruptive to life (as you can imagine) but its indestructible, does not communicate and remains motionless and unfathomable. After 7 years it moves position. After another 80 years it moves again but just one leg, after 231 years it leaves earth for good. Totally incomprehensibly alien.