I highly doubt that Vincent Rijmen and Joan Daemen themselves were influenced by the NSA in any way in the design of Rijndael, unless you believe that they influenced all the AES entrants, including Ronald Rivest (RC6) and Bruce Schneier (Twofish). I think the only influence the NSA might have had was in perhaps influencing the NIST selection process that chose Rijndael as the Advanced Encryption Standard. And in the thirteen years since it was thus chosen it has been scrutinised more thoroughly than any algorithm by the best cryptographers in the world, and well, none of the open researchers anyway have found an attack on the cipher capable of breaking it significantly. The NSA might have, but then they approved the cipher for encrypting US government classified documents (a blessing that the NSA notably did not give the original Data Encryption Standard), so I'd consider it highly unlikely that they would have done that. The risk would be too great that their method of breaking the cipher have been obtained by espionage or independently discovered by some other intelligence agency's cryptanalysts. The NSA may be evil, but no one has ever accused them of stupidity.
Given that the best cryptanalysts of the world have had thirteen years to look at it and it remains solid, I'd trust it better than the other AES candidates which have had much less scrutiny, or worse yet, a newly designed cipher that no one who knows anything has bothered to even try analysing.
The other thing is that AES is incredibly efficient even on 8-bit microcontrollers. Around the time the AES contest was ongoing, I implemented Serpent, Twofish, and Rijndael on an 8051-series microcontroller, and Rijndael was consistently the best performing cipher, so I used it in the project, and wasn't surprised to learn that it eventually got selected.