John DeChancie's Skyway Trilogy: Starrigger, Red Limit Freeway, and Paradox Alley. Here is the back cover blurb from my copy of Red Limit Freeway:
THERE'S NO SPEED LIMIT
ON THE FREEWAY TO THE END
OF THE UNIVERSE
Jake McGraw has accidentally discovered
what may be the legendary Roadmap to the
Big Bang. But how much longer can Jake
keep his battered starrig rolling with half
the galaxy after him--from insectoid aliens
and ubiquitous Roadbugs to the diabolical
Perpetually, if Jake knows what's good for
him. Because there are no safe truck stops
on the multidimensional highway where
anything goes and only one law prevails:
THOU SHALT NOT OBSTRUCT THE
So the main characters are driving a big truck on an interstellar highway patrolled by mysterious "Roadbugs". There is plenty of time travel going on: right at the beginning, Jake picks up a hitchhiker named Darla, who has met him before, but he hasn't met her before. The funny-looking non-humanoid character shows up in chapter 4 of Red Limit Freeway:
Suddenly, something crashed through the undergrowth and barged into the clearing.
I have an image of an animal somewhere between a giraffe and a kangaroo, with the head of a very strange dog. It resembled no other alien fauna I had ever seen. Yes, the head of a dog . . . well, not a dog, really. It had horn-shaped ears. Horn, as in musical instrument. Sticking out of either side of the small head. Must have been eight or nine feet tall. And it had purple and pink splotches over its inert yellow plasticine skin. It walked on two legs. and had two prehensile forelegs that dangled spastically as it moved.
Now, this is the part I'm really not sure about at all.
The beast stopped in its tracks when it saw me. It gave a yawp and said, "Oh! Dearie me, dearie me! Oh! Oh! Goodness gracious!"
Then it turned and ran, disappearing into the trees.
Our heroes see a Roadbug reproduce in chapter 17 of Red Limit Freeway:
Our tour of the area continued desultorily. We rolled by several kilometers of empty bays . . . until we found one occupied.
By a Roadbug.
Rather, one-and-a-half Roadbugs.
"It's dividing!" Roland gasped in wonder. "Reproducing itself!"
I yelled for everyone to come forward.
The thing in the bay had developed a deep rift down its back and had expanded to half again its normal width. It was a stunningly simple and effective method of parturition.
"Now we know they aren't machines," John said in awe.
"Do we?" I asked.
Roland shook his head at the immense bifurcated blob within the enclosure. "But complex organisms can't reproduce that way! They just don't!"
"Maybe they're all one cell," Sean suggested.
"Impossible," Roland answered, sounding less than certain.