Bruckner's symphonies are very outwardly logical. Their development is usually displayed right on the surface as one version of a motif turns, by steps, into another version. The rather harsh sound of his orchestration is part of the single-mindedness of his music, which is always doing just what it appears to be (although that is sometimes more complicated than others, as in the funereal chorale/polka second theme group of the finale of the third). His music is like Baroque music in that it represents nothing less than a thorough working-out of the motifs that he uses, often by combination with other motifs and presentation of those motifs in various key areas.
I think one of the obstacles to people's appreciation of Bruckner is the relative lack of perfect authentic cadences, and the way these are used within the music. The opening of the Fourth, for example, is a single melody that cadences plagally a few times before finally reaching its first V7-I at the first tutti, and even there, it is not stated outright so much as implied, and the key immediately begins to move off towards the dominant. The first movement actually ends with a plagal cadence from the minor IV, and the finale, even more oddly, from the flatted II, which can make the listener not accustomed to Bruckner's harmony feel like the music suddenly comes to a stop without having resolved. He treats pretty much every passing key as if it were stable, which gives the construction of his music something of a block-like feel at times (but this is also related to the Baroque elements mentioned above), and his treatment of dissonance is idiosyncratic (he had a particular fondness for the flatted second, melodically and harmonically).
Overall, Bruckner's music is solid and sturdy. There are folk-like moments in his works, but their tone is overwhelmingly reverent and, despite their outward bursts of violence, inwardly quite contented.
Mahler, on the other hand, is not any of the above. His music is worked out underneath the surface, and its logic is usually not immediately apparent. His orchestration is micro-managed to a degree far surpassing even Strauss and Wagner, and he even goes so far as to distribute parts of a single line across different instruments and instrumental groups. His music feels spontaneous and "classical" where Bruckner's is measured and "baroque". Mahler wrote (decidedly secular) lieder as his important secondary genre, while Bruckner wrote masses and motets.
I think that there are several obstacles to people appreciating Mahler's music, and the outward contrasts he employs are actually among the least of them (they are simply the thing that people notice). The first, and most important, is the lack of literal repetition. Mahler would develop his motifs over the course of a movement, and whole sections will be based on a derivation rather than the original, so if the connection is not sensed (consciously or unconsciously), these might seem like unconnected asides. The thing is that these derivations are not worked out in steps, but they tend to happen simultaneously with other important musical events and all at once. Formally, Mahler's music is based upon classical models, but these were always adapted rather than used as strict templates, and the adaptation might extend so far as to open a movement in the "wrong" key (like the Seventh or the Fourth), or even to end a work in a different tonal center from that of its first movement (like the Second, the Fifth, or the Ninth).
Overall, Mahler's music is searching and spontaneous. There is a sense of play in all of his works (even or especially at their most cynical and sarcastic), and an innate lyricism that proliferates throughout even the subordinate lines in any of his prismatic textures.