I'd think that the Choose Your Own Adventure would work fine on the Sony -- it could be implemented with just straight links, which the Reader supports.
True interactive fiction would be cool, believe it or not, I kinda miss those games.
It might be doable if the app which ran it could have some sort of input mechanism, but it would be pretty rough going though.