Thanks to the recommendations in the forums I made it to Big Bend NP in Southern Texas/Rio Grande right on the Mexican border. Next to Roman, I got recommend this area second by an old friend from Calgary/Canada as his favourit place in Texas, so I figured it must have been worth the long drive. In case anyone familiar with the area:
We did two seperate trips. First (no boating), hiked up Pine Canyon trail, connected off trail to the high chisos trail system (via Boot Canyon), did a classic rim loop there, decenteted Juniper canyon and got back to the car near Nugent Mtn (again 5 miles off trail, lots of acti - ouch). Pictures:
http://picasaweb.google.de/sven.schellin/BigBend2PineCanyonChisosMountainsDesertCountry?authkey=Gv1sRgCMvqoO2I5MSfkAE
Second, we drove to Rio Grande village, set in by pack rafts, floated the Boquillas Canyon, no whitewater, but did not lack the excitement either:
We planned to get out of the Canyon at Marufo Vega Trail South fork, but we learned the trail is not only incoorrectly marked on USGS Maps, but also is a mess with game trails, no chance to get a mark in this rugged and highly diversified area. Floated further in hope of Marufo Vega Trail North fork is better marked. There were only this two exits out of the Canyon and we had to fix a flat tire, and a plane to catch the next day. Quite an adventure. Pictures:
http://picasaweb.google.de/sven.schellin/BigBend3BoquillasCanyonMarufoVega?authkey=Gv1sRgCKSpvqGVm8fsqAE#
All in all 4 full days, and rougly 60 + miles. Driving from Houston 600+ miles was not as bad as I expected. Easy compared to Europe! Got one flat tire on gravel roads though.
No bears or cougars, but one bobcat. Enjoyed the lower desert as much as the high woodland. And the Canyon, wow, a classic all American. Nice winter break (temps up to over 70° F) and exotic scenery. Some rain in the beginning, then clear blue sky all day - got sun burned. Camping under stars, (what a star sky!). Took advantage of detailed planning on food, water, and maps/directions.
To my experience, the American NP Sytem is quite effiecient, but not encouraging to form own ideas. All the regulations were putting me a bit off in my desire of a feeling of discovery and freedom. I am simply not used to permits, backcountry travel sheme. I did not like how they direct you to “consume” the features of the park, however, also learned how avoid this 
We still have Winter here in Germany, had one melt down in beetween, but back on XC Skis now.
Cheers,
Sven